結果
| 問題 | No.1526 Sum of Mex 2 |
| ユーザー |
 kwm_t
|
| 提出日時 | 2026-08-09 00:53:43 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 124 ms / 3,000 ms |
| + 763µs | |
| コード長 | 8,749 bytes |
| 記録 | |
| コンパイル時間 | 3,459 ms |
| コンパイル使用メモリ | 365,904 KB |
| 実行使用メモリ | 20,992 KB |
| 最終ジャッジ日時 | 2026-08-09 00:53:59 |
| 合計ジャッジ時間 | 7,539 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 32 |
ソースコード
#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]--;
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 = (long long)n * (n + 1) / 2;
rep(i, n) {
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 });
ans += (long long)n * n - seg.all_prod().sum;
}
cout << ans << endl;
return 0;
}