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

• 問題: No.3466 Mex Ranges
• ユーザー: kwm_t
• 提出日時: 2026-08-09 01:24:07
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 395 ms / 3,000 ms
• コード長: 8,846 bytes
• コンパイル時間: 4,427 ms
• コンパイル使用メモリ: 365,904 KB
• 実行使用メモリ: 41,216 KB
• 最終ジャッジ日時: 2026-08-09 01:24:23
• 合計ジャッジ時間: 15,966 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_0

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

ソースコード

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; }
#ifndef KWM_T_SEGTREE_LAZY_SEGTREE_BEATS_HPP
#define KWM_T_SEGTREE_LAZY_SEGTREE_BEATS_HPP

#include <bits/stdc++.h>

/**
 * @brief Segment Tree Beats (ACL風 lazy_segtree 拡張)
 *
 * mapping が (S, bool) を返し、失敗時に push することで
 * Segment Tree Beats を実現する
 *
 * 典型用途:
 *   - range chmin / chmax / add / sum
 *   - 区間制約付き更新（破壊的更新を伴うもの）
 *
 * 計算量:
 *   - amortized O(log N)
 *
 * @tparam S モノイド（ノード情報）
 * @tparam op S × S → S
 * @tparam e 単位元
 * @tparam F 遅延作用素
 * @tparam mapping (F, S) → (S, bool)
 *           bool = true のとき「このノードでは処理できない」
 * @tparam composition F ∘ F
 * @tparam id 単位作用素
 *
 * 制約 / 注意:
 *   - mapping が失敗するケースを正しく実装すること
 *   - composition は f(g(x)) の順
 *
 * 使用例:
 *   using Seg = lazy_segtree<...>;
 *   Seg seg(n);
 *
 * verified:
 *   - https://atcoder.jp/contests/abc430/submissions/74233474
 */

namespace kwm_t::segtree {

inline unsigned int bit_ceil(unsigned int n) {
	unsigned int x = 1;
	while (x < n) x <<= 1;
	return x;
}

inline int countr_zero(unsigned int n) {
#ifdef _MSC_VER
	unsigned long index;
	_BitScanForward(&index, n);
	return index;
#else
	return __builtin_ctz(n);
#endif
}

#if __cplusplus >= 201703L

template <class S,
	auto op,
	auto e,
	class F,
	auto mapping,
	auto composition,
	auto id>
struct lazy_segtree

#else

template <class S,
	S(*op)(S, S),
	S(*e)(),
	class F,
	std::pair<S, bool>(*mapping)(F, S),
	F(*composition)(F, F),
	F(*id)()>
struct lazy_segtree

#endif
{
public:
	lazy_segtree() : lazy_segtree(0) {}
	explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}

	explicit lazy_segtree(const std::vector<S>& v) : _n((int)v.size()) {
		size = (int)bit_ceil((unsigned int)_n);
		log = countr_zero((unsigned int)size);
		d.assign(2 * size, e());
		lz.assign(size, id());

		for (int i = 0; i < _n; i++) d[size + i] = v[i];
		for (int i = size - 1; i >= 1; i--) update(i);
	}

	void set(int p, S x) {
		assert(0 <= p && p < _n);
		p += size;
		for (int i = log; i >= 1; i--) push(p >> i);
		d[p] = x;
		for (int i = 1; i <= log; i++) update(p >> i);
	}

	S get(int p) {
		assert(0 <= p && p < _n);
		p += size;
		for (int i = log; i >= 1; i--) push(p >> i);
		return d[p];
	}

	S prod(int l, int r) {
		assert(0 <= l && l <= r && r <= _n);
		if (l == r) return e();

		l += size;
		r += size;

		for (int i = log; i >= 1; i--) {
			if (((l >> i) << i) != l) push(l >> i);
			if (((r >> i) << i) != r) push((r - 1) >> i);
		}

		S sml = e(), smr = e();
		while (l < r) {
			if (l & 1) sml = op(sml, d[l++]);
			if (r & 1) smr = op(d[--r], smr);
			l >>= 1;
			r >>= 1;
		}

		return op(sml, smr);
	}

	S all_prod() { return d[1]; }

	void apply(int p, F f) {
		assert(0 <= p && p < _n);
		p += size;
		for (int i = log; i >= 1; i--) push(p >> i);
		d[p] = mapping(f, d[p]).first;
		for (int i = 1; i <= log; i++) update(p >> i);
	}

	void apply(int l, int r, F f) {
		assert(0 <= l && l <= r && r <= _n);
		if (l == r) return;

		l += size;
		r += size;

		for (int i = log; i >= 1; i--) {
			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) all_apply(l++, f);
			if (r & 1) all_apply(--r, f);
			l >>= 1;
			r >>= 1;
		}
		l = l2;
		r = r2;

		for (int i = 1; i <= log; i++) {
			if (((l >> i) << i) != l) update(l >> i);
			if (((r >> i) << i) != r) update((r - 1) >> i);
		}
	}

private:
	int _n, size, log;
	std::vector<S> d;
	std::vector<F> lz;

	void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }

	void all_apply(int k, F f) {
		auto [x, fail] = mapping(f, d[k]);
		d[k] = x;
		if (k < size) {
			lz[k] = composition(f, lz[k]);
			if (fail) {
				push(k);
				update(k);
			}
		}
	}

	void push(int k) {
		all_apply(2 * k, lz[k]);
		all_apply(2 * k + 1, lz[k]);
		lz[k] = id();
	}
};

} // namespace kwm_t::segtree::beats

#endif // KWM_T_SEGTREE_LAZY_SEGTREE_BEATS_HPP

#ifndef KWM_T_SEGTREE_BEATS_VARIANTS_HPP
#define KWM_T_SEGTREE_BEATS_VARIANTS_HPP

#include <vector>
#include <algorithm>
// #include "lazy_segtree_beats.hpp"

/**
 * @brief Segment Tree Beats 用の典型パターン
 *
 * 提供:
 *   - Range Chmin / Sum
 *   - Range Chmax / Sum
 *
 * 計算量:
 *   - amortized O(log N)
 *
 * 注意:
 *   - mapping は失敗時に {x, true} を返すこと
 *   - 値は long long 前提
 *
 * verified:
 *   -
 */

namespace kwm_t::segtree::beats {

// ================= Range Chmin / Sum =================
namespace RangeChminRangeSum {

struct S {
	long long sum;
	long long max1, max2;
	int maxc;
	int size;
};

struct F {
	long long x;
};

S op(S a, S b) {
	S res;
	res.sum = a.sum + b.sum;
	res.size = a.size + b.size;

	if (a.max1 > b.max1) {
		res.max1 = a.max1;
		res.maxc = a.maxc;
		res.max2 = std::max(a.max2, b.max1);
	}
	else if (a.max1 < b.max1) {
		res.max1 = b.max1;
		res.maxc = b.maxc;
		res.max2 = std::max(a.max1, b.max2);
	}
	else {
		res.max1 = a.max1;
		res.maxc = a.maxc + b.maxc;
		res.max2 = std::max(a.max2, b.max2);
	}
	return res;
}

S e() {
	return { 0, -(long long)4e18, -(long long)4e18, 0, 0 };
}

std::pair<S, bool> mapping(F f, S x) {
	if (x.max1 <= f.x) return { x, false };
	if (x.max2 < f.x) {
		long long diff = x.max1 - f.x;
		x.sum -= diff * x.maxc;
		x.max1 = f.x;
		return { x, false };
	}
	return { x, true }; // fail
}

F composition(F f, F g) {
	return { std::min(f.x, g.x) };
}

F id() {
	return { (long long)4e18 };
}

using segtree = lazy_segtree<S, op, e, F, mapping, composition, id>;

std::vector<S> init(const std::vector<long long>& v) {
	int n = v.size();
	std::vector<S> res(n);
	for (int i = 0; i < n; i++) {
		res[i] = { v[i], v[i], -(long long)4e18, 1, 1 };
	}
	return res;
}
}

// ================= Range Chmax / Sum =================
namespace RangeChmaxRangeSum {

struct S {
	long long sum;
	long long min1, min2;
	int minc;
	int size;
};

struct F {
	long long x;
};

S op(S a, S b) {
	S res;
	res.sum = a.sum + b.sum;
	res.size = a.size + b.size;

	if (a.min1 < b.min1) {
		res.min1 = a.min1;
		res.minc = a.minc;
		res.min2 = std::min(a.min2, b.min1);
	}
	else if (a.min1 > b.min1) {
		res.min1 = b.min1;
		res.minc = b.minc;
		res.min2 = std::min(a.min1, b.min2);
	}
	else {
		res.min1 = a.min1;
		res.minc = a.minc + b.minc;
		res.min2 = std::min(a.min2, b.min2);
	}
	return res;
}

S e() {
	return { 0, (long long)4e18, (long long)4e18, 0, 0 };
}

std::pair<S, bool> mapping(F f, S x) {
	if (x.min1 >= f.x) return { x, false };
	if (x.min2 > f.x) {
		long long diff = f.x - x.min1;
		x.sum += diff * x.minc;
		x.min1 = f.x;
		return { x, false };
	}
	return { x, true };
}

F composition(F f, F g) {
	return { std::max(f.x, g.x) };
}

F id() {
	return { -(long long)4e18 };
}

using segtree = lazy_segtree<S, op, e, F, mapping, composition, id>;

std::vector<S> init(const std::vector<long long>& v) {
	int n = v.size();
	std::vector<S> res(n);
	for (int i = 0; i < n; i++) {
		res[i] = { v[i], v[i], (long long)4e18, 1, 1 };
	}
	return res;
}
}

} // namespace kwm_t::segtree::beats

#endif // KWM_T_SEGTREE_BEATS_VARIANTS_HPP

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n; cin >> n;
	vector<int>a(n);
	vector<vector<int>>idx(n + 1);
	rep(i, n) {
		cin >> a[i];
		//a[i]--;
		if (a[i] <= n)idx[a[i]].push_back(i);
	}
	using namespace kwm_t::segtree::beats;
	vector<long long>ini(n);
	rep(i, n)ini[i] = i;
	RangeChmaxRangeSum::segtree seg(RangeChmaxRangeSum::init(ini));
	long long ans = 0;
	vector<long long> d(n + 2);
	d[0] = (long long)n * (n + 1) / 2;
	rep(i, n + 1) {
		int pre = 0;
		for (auto idx : idx[i]) {
			seg.apply(pre, idx + 1, RangeChmaxRangeSum::F{ idx });
			pre = idx + 1;
		}
		seg.apply(pre, n, RangeChmaxRangeSum::F{ n });
		d[i + 1] = (long long)n * n - seg.all_prod().sum;
	}
	rep(i, n + 1) {
		cout << d[i] - d[i + 1] << endl;
	}
	return 0;
}