#1193118 (C++23) No.3466 Mex Ranges

• 問題: No.3466 Mex Ranges
• ユーザー: fura
• 提出日時: 2026-10-15 01:44:57
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 465 ms / 3,000 ms
• コード長: 15,238 bytes
• コンパイル時間: 2,733 ms
• コンパイル使用メモリ: 363,176 KB
• 実行使用メモリ: 33,080 KB
• 最終ジャッジ日時: 2026-10-15 01:45:18
• 合計ジャッジ時間: 8,886 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge5_0

ファイルパターン	結果
sample	AC * 1
other	AC * 22

ソースコード

// https://github.com/fura2/cp-library

#include <bits/stdc++.h>

#ifdef LOCAL
#include <template/debug.hpp>
#else
#define show(...) ((void)0)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#endif


inline constexpr int INF = 1'010'000'000;
inline constexpr long long LINF = 4'000'000'000'000'000'000LL;
inline constexpr double DINF = 1e100;


template <typename T>
struct Input {
  static T read() {
    T x;
    std::cin >> x;
    return x;
  }
};

template <typename T, typename U>
struct Input<std::pair<T, U>> {
  static std::pair<T, U> read() {
    return std::pair{Input<T>::read(), Input<U>::read()};
  }
};

template <typename T>
struct Input<std::vector<T>> {
  static std::vector<T> read(int n) {
    std::vector<T> v;
    v.reserve(n);
    for (int i = 0; i < n; ++i) {
      v.push_back(Input<T>::read());
    }
    return v;
  }

  static std::vector<T> read(int n, int offset) {
    std::vector<T> v;
    v.reserve(n);
    for (int i = 0; i < n; ++i) {
      v.push_back(Input<T>::read() - offset);
    }
    return v;
  }
};

template <typename T, typename... Args>
T input(Args&&... args) {
  return Input<T>::read(std::forward<Args>(args)...);
}

template <typename T>
struct Output {
  static void write(const T& x) { std::cout << x; }
};

template <typename T, typename U>
struct Output<std::pair<T, U>> {
  static void write(const std::pair<T, U>& p) {
    Output<T>::write(p.first);
    std::cout << " ";
    Output<U>::write(p.second);
  }
};

template <typename T, std::size_t N>
struct Output<T[N]> {
  static void write(const T (&a)[N]) {
    for (int i = 0; const auto& x: a) {
      if (i > 0) std::cout << " ";
      Output<T>::write(x);
      ++i;
    }
  }

  static void write(const T (&a)[N], int offset)
    requires requires(const T& x, int n) { x + n; }
  {
    for (int i = 0; const auto& x: a) {
      if (i > 0) std::cout << " ";
      Output<T>::write(x + offset);
      ++i;
    }
  }
};

template <typename T>
struct Output<std::vector<T>> {
  static void write(const std::vector<T>& v) {
    for (int i = 0; const auto& x: v) {
      if (i > 0) std::cout << " ";
      Output<T>::write(x);
      ++i;
    }
  }

  static void write(const std::vector<T>& v, int offset)
    requires requires(const T& x, int n) { x + n; }
  {
    for (int i = 0; const auto& x: v) {
      if (i > 0) std::cout << " ";
      Output<T>::write(x + offset);
      ++i;
    }
  }
};

template <typename T, typename... Args>
void output(const T& x, Args&&... args) {
  Output<T>::write(x, std::forward<Args>(args)...);
#ifdef LOCAL
  std::cout << std::endl;
#else
  std::cout << "\n";
#endif
}

inline void output(const char* s) { output<const char*>(s); }

#define impl_overload4(a, b, c, d, e, ...) e

// clang-format off
#define impl_rep4(i, a, b, c) for (int i = (a); i < (b); i += (c))
#define impl_rep3(i, a, b) impl_rep4(i, a, b, 1)
#define impl_rep2(i, n) impl_rep3(i, 0, n)
#define impl_rep1(n) for (int _ = 0; _ < (n); ++_)
#define rep(...) impl_overload4(__VA_ARGS__, impl_rep4, impl_rep3, impl_rep2, impl_rep1)(__VA_ARGS__)

#define impl_rrep4(i, a, b, c) for (int i = (b) - 1; i >= (a); i -= (c))
#define impl_rrep3(i, a, b) impl_rrep4(i, a, b, 1)
#define impl_rrep2(i, n) impl_rrep3(i, 0, n)
#define rrep(...) impl_overload4(__VA_ARGS__, impl_rrep4, impl_rrep3, impl_rrep2)(__VA_ARGS__)
// clang-format on

template <typename T>
int bit(T x, unsigned int k) {
  return (x >> k) & 1;
}

template <typename T>
bool chmax(T& a, const T& b) {
  return a < b ? a = b, true : false;
}
template <typename T>
bool chmin(T& a, const T& b) {
  return b < a ? a = b, true : false;
}

inline void yesno(bool b) { output(b ? "Yes" : "No"); }
inline void yes() { yesno(true); }
inline void no() { yesno(false); }
inline void alicebob(bool b) { output(b ? "Alice" : "Bob"); }
inline void alice() { alicebob(true); }
inline void bob() { alicebob(false); }

inline const auto io_setup = [] {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout << std::fixed << std::setprecision(12);
  return 0;
}();

using uint = unsigned int;
using lint = long long;
using ulint = unsigned long long;

using namespace std;

// #define MULTI_TESTCASE



#include <concepts>


template <typename T>
inline constexpr auto id_zero = nullptr;
template <>
inline constexpr auto id_zero<int> = []() { return 0; };
template <>
inline constexpr auto id_zero<long long> = []() { return 0LL; };
template <>
inline constexpr auto id_zero<double> = []() { return 0.0; };

template <typename T>
inline constexpr auto id_one = nullptr;
template <>
inline constexpr auto id_one<int> = []() { return 1; };
template <>
inline constexpr auto id_one<long long> = []() { return 1LL; };
template <>
inline constexpr auto id_one<double> = []() { return 1.0; };

template <typename T>
inline constexpr auto id_inf = nullptr;
template <>
inline constexpr auto id_inf<int> = []() { return INF; };
template <>
inline constexpr auto id_inf<long long> = []() { return LINF; };
template <>
inline constexpr auto id_inf<double> = []() { return DINF; };

template <typename T>
  requires requires() {
    { id_inf<T>() } -> std::same_as<T>;
  } && requires(const T& a) {
    { -a } -> std::same_as<T>;
  }
inline constexpr auto id_neg_inf = []() -> T { return -id_inf<T>(); };


template <typename T>
  requires requires(const T& a, const T& b) {
    { a + b } -> std::same_as<T>;
  }
inline constexpr auto op_add = std::plus<T>{};

template <typename T>
  requires requires(const T& a, const T& b) {
    { a * b } -> std::same_as<T>;
  }
inline constexpr auto op_mul = std::multiplies<T>{};

template <typename T>
  requires requires(const T& a, const T& b) {
    { a < b } -> std::same_as<bool>;
  }
inline constexpr auto op_max =
    [](const T& a, const T& b) -> T { return a < b ? b : a; };

template <typename T>
  requires requires(const T& a, const T& b) {
    { a < b } -> std::same_as<bool>;
  }
inline constexpr auto op_min =
    [](const T& a, const T& b) -> T { return b < a ? b : a; };

template <typename T>
  requires requires(const T& a) {
    { -a } -> std::same_as<T>;
  }
inline constexpr auto op_neg = std::negate<T>{};


template <typename T, auto Op, auto Id>
  requires(
      requires {
        { Id() } -> std::same_as<T>;
      } &&
      requires(const T& a, const T& b) {
        { Op(a, b) } -> std::same_as<T>;
      })
class MonoidImpl {
 public:
  MonoidImpl(): x{Id()} {}
  MonoidImpl(const T& x): x{x} {}
  MonoidImpl(T&& x): x{std::move(x)} {}

  friend MonoidImpl operator*(const MonoidImpl& m, const MonoidImpl& n) {
    return MonoidImpl{Op(m.x, n.x)};
  }
  static MonoidImpl identity() { return MonoidImpl{Id()}; }

  const T& unwrap() const { return x; }
  T& unwrap() { return x; }

  friend std::string pretty(const MonoidImpl& m)
    requires requires(const MonoidImpl& m) {
      { pretty(m.unwrap()) } -> std::same_as<std::string>;
    }
  {
    return pretty(m.unwrap());
  }

 private:
  T x;
};

template <typename T>
using AddMonoid = MonoidImpl<T, op_add<T>, id_zero<T>>;

#include <optional>


namespace last_monoid_detail {

template <typename T>
inline constexpr auto op =
    [](const std::optional<T>& a, const std::optional<T>& b) {
      return b.has_value() ? b : a;
    };

template <typename T>
inline constexpr auto id = []() -> std::optional<T> { return std::nullopt; };

}  // namespace last_monoid_detail

template <typename T>
using LastMonoid = MonoidImpl<std::optional<T>,
                              last_monoid_detail::op<T>,
                              last_monoid_detail::id<T>>;






template <typename S>
concept Semigroup = requires(const S& a, const S& b) {
  { a * b } -> std::same_as<S>;
};

template <typename M>
concept IdempotentSemigroup = Semigroup<M>;

template <typename M>
concept Monoid = Semigroup<M> && requires {
  { M::identity() } -> std::same_as<M>;
};

template <typename M>
concept CommutativeMonoid = Monoid<M>;

template <typename X, Monoid F, auto Act>
  requires requires(const X& x, const F& f) {
    { Act(x, f) } -> std::same_as<X>;
  }
class MonoidActionImpl {
 public:
  using value_type = X;
  using action_type = F;

  inline static const auto act = Act;
};



template <Monoid M, Monoid N>
class PairMonoid {
 public:
  M first;
  N second;

  PairMonoid(): first{M::identity()}, second{N::identity()} {}

  template <typename T = M, typename U = N>
    requires std::constructible_from<M, T&&> && std::constructible_from<N, U&&>
  PairMonoid(T&& x, U&& y)
      : first(std::forward<T>(x)), second(std::forward<U>(y)) {}

  template <typename T = M, typename U = N>
    requires std::constructible_from<M, const T&> &&
                 std::constructible_from<N, const U&>
  PairMonoid(const std::pair<T, U>& p): first(p.first), second(p.second) {}

  template <typename T = M, typename U = N>
    requires std::constructible_from<M, T&&> && std::constructible_from<N, U&&>
  PairMonoid(std::pair<T, U>&& p)
      : first(std::forward<T>(p.first)), second(std::forward<U>(p.second)) {}

  friend PairMonoid operator*(const PairMonoid& p, const PairMonoid& q) {
    return PairMonoid{p.first * q.first, p.second * q.second};
  }
  static PairMonoid identity() { return PairMonoid{}; }

  friend std::string pretty(const PairMonoid& p)
    requires requires(const M& m) {
      { pretty(m) } -> std::same_as<std::string>;
    } && requires(const N& n) {
      { pretty(n) } -> std::same_as<std::string>;
    }
  {
    return "(" + pretty(p.first) + ", " + pretty(p.second) + ")";
  }
};

namespace sum_assign_monoid_action_detail {

template <typename T>
using ValueMonoid = PairMonoid<AddMonoid<T>, AddMonoid<int>>;

template <typename T>
using ActionMonoid = LastMonoid<T>;

template <typename T>
inline constexpr auto act =
    [](const ValueMonoid<T>& x, const ActionMonoid<T>& f) {
      return f.unwrap().has_value()
                 ? ValueMonoid<T>{x.second.unwrap() * f.unwrap().value(),
                                  x.second.unwrap()}
                 : x;
    };

}  // namespace sum_assign_monoid_action_detail

template <typename T>
using SumAssignMonoidAction =
    MonoidActionImpl<sum_assign_monoid_action_detail::ValueMonoid<T>,
                     sum_assign_monoid_action_detail::ActionMonoid<T>,
                     sum_assign_monoid_action_detail::act<T>>;

#include <bit>




template <typename A>
concept MonoidAction =
    requires {
      typename A::value_type;
      typename A::action_type;
    } && Monoid<typename A::action_type> &&
    requires(const typename A::value_type& x,
             const typename A::action_type& f) {
      { A::act(x, f) } -> std::same_as<typename A::value_type>;
    };

template <typename A>
concept MonoidActionOnMonoid =
    MonoidAction<A> && Monoid<typename A::value_type>;

template <MonoidActionOnMonoid A>
class LazySegmentTree {
  using X = A::value_type;
  using F = A::action_type;

 public:
  explicit LazySegmentTree(int n)
      : n{n},
        sz(std::bit_ceil<unsigned int>(n)),
        h{std::bit_width<unsigned int>(sz)},
        x(2 * sz, X::identity()),
        f(sz, F::identity()) {}

  template <typename T = X>
    requires std::constructible_from<X, const T&>
  explicit LazySegmentTree(const std::vector<T>& a)
      : n(a.size()),
        sz(std::bit_ceil<unsigned int>(n)),
        h{std::bit_width<unsigned int>(sz)},
        x(2 * sz, X::identity()),
        f(sz, F::identity()) {
    for (int i = 0; i < n; ++i) {
      x[sz + i] = X{a[i]};
    }
    for (int u = sz - 1; u > 0; --u) {
      x[u] = x[u << 1] * x[(u << 1) | 1];
    }
  }

  int size() const { return n; }

  const X& get(int i) const {
    assert(0 <= i && i < n);
    int u = sz + i;
    push(u);
    return x[u];
  }

  template <typename T = X>
    requires std::constructible_from<X, const T&>
  void set(int i, const T& v) {
    assert(0 <= i && i < n);
    int u = sz + i;
    push(u);
    x[u] = X{v};
    fix(u);
  }

  const X& fold() const { return x[1]; }

  X fold(int l, int r) const {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) return X::identity();
    l += sz;
    r += sz;

    push(l);
    push(r - 1);

    X lcum = X::identity(), rcum = X::identity();
    while (l < r) {
      if (l & 1) {
        lcum = lcum * x[l];
        ++l;
      }
      if (r & 1) {
        --r;
        rcum = x[r] * rcum;
      }
      l >>= 1;
      r >>= 1;
    }

    return lcum * rcum;
  }

  template <typename T = F>
    requires std::constructible_from<F, const T&>
  void apply(int l, int r, const T& v) {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) return;
    l += sz;
    r += sz;

    push(l);
    push(r - 1);

    int l2 = l, r2 = r;
    while (l < r) {
      if (l & 1) {
        calc(l, F{v});
        ++l;
      }
      if (r & 1) {
        --r;
        calc(r, F{v});
      }
      l >>= 1;
      r >>= 1;
    }
    l = l2;
    r = r2;

    fix(l);
    fix(r - 1);
  }

  template <typename G>
    requires std::predicate<G&, X>
  int max_right(int l, G g) const {
    assert(0 <= l && l <= n);
    assert(g(X::identity()));
    // TODO
  }

  template <typename G>
    requires std::predicate<G&, X>
  int min_left(int r, G g) const {
    assert(0 <= r && r <= n);
    assert(g(X::identity()));
    // TODO
  }

  friend std::string pretty(const LazySegmentTree& S) {
    if constexpr (requires(const X& x) {
                    { pretty(x) } -> std::same_as<std::string>;
                  }) {
      std::string s = "[";
      for (int i = 0; i < S.size(); ++i) {
        s += (i == 0 ? "" : ", ") + pretty(S.get(i));
      }
      s += "]";
      return s;
    }
    return "[" + std::to_string(S.size()) + " element(s)]";
  }

 private:
  int n, sz, h;
  mutable std::vector<X> x;
  mutable std::vector<F> f;

  void fix(int u) {
    while (u > 1) {
      u >>= 1;
      x[u] = A::act(x[u << 1] * x[(u << 1) | 1], f[u]);
    }
  }

  void push(int u) const {
    for (int k = h - 1; k > 0; --k) {
      int v = u >> k;
      calc(v << 1, f[v]);
      calc((v << 1) | 1, f[v]);
      f[v] = F::identity();
    }
  }

  void calc(int u, const F& g) const {
    x[u] = A::act(x[u], g);
    if (u < sz) {
      f[u] = f[u] * g;
    }
  }
};

#include <format>

void testcase();

int main() {
#ifndef MULTI_TESTCASE
  testcase();
#else
  auto t = input<int>();
  rep (i, t) {
#ifdef LOCAL
    std::cerr << std::format("\033[36mCase #{}\033[0m\n", i + 1);
#endif
    testcase();
  }
#endif
  return 0;
}

void testcase() {
  auto n = input<lint>();
  auto a = input<vector<int>>(n);

  vector pos(n + 1, vector<int>());
  rep (i, n) pos[min<lint>(a[i], n)].emplace_back(i);
  rep (k, n + 1) pos[k].emplace_back(n);  // sentinel

  vector<pair<lint, int>> data(n);
  rep (i, n) data[i] = {i, 1};
  LazySegmentTree<SumAssignMonoidAction<lint>> S(data);

  vector<lint> f(n + 2);
  rep (k, n + 1) {
    f[k] = n * n - S.fold().first.unwrap();

    int pre = 0;
    for (int i: pos[k]) {
      if (pre < n && S.get(pre).first.unwrap() < i) {
        int lo = pre, hi = i;
        while (hi - lo > 1) {
          int mi = (lo + hi) / 2;
          (S.get(mi).first.unwrap() >= i ? hi : lo) = mi;
        }
        S.apply(pre, hi, i);
      }
      pre = i + 1;
    }
  }
  rep (i, n + 1) output(f[i] - f[i + 1]);
}