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

• 問題: No.3466 Mex Ranges
• ユーザー: hato336
• 提出日時: 2026-02-28 17:58:53
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 604 ms / 3,000 ms
• コード長: 5,354 bytes
• コンパイル時間: 4,140 ms
• コンパイル使用メモリ: 361,532 KB
• 実行使用メモリ: 55,216 KB
• 最終ジャッジ日時: 2026-02-28 17:59:12
• 合計ジャッジ時間: 17,539 ms
• ジャッジサーバーID （参考情報）: judge5 / judge7

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for(ll i = (a)-1; i >= (b); i--)
#define fore(e, v) for(auto&& e : v)
#define all(a) begin(a), end(a)
#define si(a) (int)(size(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back

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

const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;

#define i128 __int128_t

struct Segtree_beats {
   ll op(int type, ll x, ll y) { return type ? min(x, y) : max(x, y); }
   bool cmp(int type, ll x, ll y) { return type ? x < y : x > y; }
   struct alignas(32) Node {
      ll sum = 0;
      ll a1[2] = {}, a2[2] = {-INFL, INFL}, ac[2] = {1, 1}, add = 0;
   };

   vector<Node> v;
   ll n, log, e[3] = {-INFL, INFL, 0};

   Segtree_beats() {}
   Segtree_beats(int n) : Segtree_beats(vl(n)) {}
   Segtree_beats(const vl& a) {
      n = 1, log = 0;
      while(n < si(a)) n <<= 1, log++;
      v.resize(2 * n);
      rep(i, si(a)) { v[i + n].sum = v[i + n].a1[0] = v[i + n].a1[1] = a[i]; }
      per(i, n, 1) update(i);
   }

   // 0 : add, 1 : chmin, 2 : chmax, 3 : update
   template<int cmd> void apply(int l, int r, ll x) {
      if(l == r) return;
      l += n, r += n;
      per(i, log + 1, 1) {
         if(((l >> i) << i) != l) push(l >> i);
         if(((r >> i) << i) != r) push((r - 1) >> i);
      }
      {
         int l2 = l, r2 = r;
         while(l < r) {
            if(l & 1) _apply<cmd>(l++, x);
            if(r & 1) _apply<cmd>(--r, x);
            l >>= 1;
            r >>= 1;
         }
         l = l2;
         r = r2;
      }
      rep(i, 1, log + 1) {
         if(((l >> i) << i) != l) update(l >> i);
         if(((r >> i) << i) != r) update((r - 1) >> i);
      }
   }
   // 0 : max, 1 : min, 2 : sum
   template<int cmd> ll fold(int l, int r) {
      if(l == r) return e[cmd];
      l += n, r += n;
      per(i, log + 1, 1) {
         if(((l >> i) << i) != l) push(l >> i);
         if(((r >> i) << i) != r) push((r - 1) >> i);
      }
      ll lx = e[cmd], rx = e[cmd];
      while(l < r) {
         if(l & 1) op<cmd>(lx, v[l++]);
         if(r & 1) op<cmd>(rx, v[--r]);
         l >>= 1;
         r >>= 1;
      }
      if constexpr(cmd <= 1) lx = op(cmd, lx, rx);
      if constexpr(cmd == 2) lx += rx;
      return lx;
   }

   private:
   void update(int k) {
      Node& p = v[k];
      Node& l = v[k * 2 + 0];
      Node& r = v[k * 2 + 1];
      p.sum = l.sum + r.sum;
      rep(t, 2) {
         if(l.a1[t] == r.a1[t]) {
            p.a1[t] = l.a1[t];
            p.a2[t] = op(t, l.a2[t], r.a2[t]);
            p.ac[t] = l.ac[t] + r.ac[t];
         } else {
            bool f = cmp(t, l.a1[t], r.a1[t]);
            p.a1[t] = f ? l.a1[t] : r.a1[t];
            p.ac[t] = f ? l.ac[t] : r.ac[t];
            p.a2[t] = op(t, f ? r.a1[t] : l.a1[t], f ? l.a2[t] : r.a2[t]);
         }
      }
   }

   void push_add(int k, ll x) {
      Node& p = v[k];
      p.sum += x << (log + __builtin_clz(k) - 31);
      rep(t, 2) {
         p.a1[t] += x;
         if(p.a2[t] != e[t]) p.a2[t] += x;
      }
      p.add += x;
   }

   void push(int cmd, int k, ll x) {
      Node& p = v[k];
      p.sum += (x - p.a1[cmd]) * p.ac[cmd];
      if(p.a1[cmd ^ 1] == p.a1[cmd]) p.a1[cmd ^ 1] = x;
      if(p.a2[cmd ^ 1] == p.a1[cmd]) p.a2[cmd ^ 1] = x;
      p.a1[cmd] = x;
   }
   void push(int k) {
      Node& p = v[k];
      if(p.add) {
         rep(t, 2) push_add(k * 2 + t, p.add);
         p.add = 0;
      }
      rep(t, 2) rep(s, 2) if(cmp(t, v[k * 2 + s].a1[t], p.a1[t])) push(t, k * 2 + s, p.a1[t]);
   }

   void subtree_ch(int cmd, int k, ll x) {
      if(!cmp(cmd, v[k].a1[cmd], x)) return;
      if(cmp(cmd, x, v[k].a2[cmd])) { return push(cmd, k, x); }
      push(k);
      rep(t, 2) subtree_ch(cmd, k * 2 + t, x);
      update(k);
   }

   template<int cmd> inline void _apply(int k, ll x) {
      rep(i, 2) if(cmd >> i & 1) subtree_ch(i, k, x);
      if constexpr(cmd == 0) push_add(k, x);
   }

   template<int cmd> inline void op(ll& a, const Node& b) {
      if constexpr(cmd <= 1) a = op(cmd, a, b.a1[cmd]);
      if constexpr(cmd == 2) a += b.sum;
   }
};


int main() { 
    cin.tie(0)->sync_with_stdio(0);

    ll n;
    cin >> n;
    vl a(n);
    rep(i,n){
        cin >> a[i];
    }
    vector<vl> b(n+1);
    rep(i,n+1){
        b[i].push_back(-1);
    }
    rep(i,n){
        if(a[i] < n+1){
            b[a[i]].push_back(i);
        }
    }
    rep(i,n+1){
        b[i].push_back(n);
    }
    Segtree_beats sb(vl(n,n));
    rep(i,n){
        sb.apply<3>(i,i+1,i);
    }
    vl cnt(n+1,0);
    rep(i,n+1){
        rep(j,si(b[i])-1){
            sb.apply<2>(b[i][j]+1,b[i][j+1],b[i][j+1]);
        }
        cnt[i] = n * n - sb.fold<2>(0,n);
    }
    rep(i,n+1){
        cout << (i-1 >= 0 ? cnt[i-1] : n*(n+1)/2) - cnt[i] << '\n';
    }


}