本文共 4147 字，大约阅读时间需要 13 分钟。
为了解决问题，我们需要计算所有子区间的mex（最小非出现的元素）之和。直接暴力枚举所有子区间是不可能的，因此我们需要一种高效的方法。
预处理：
b，其中 b[i] 表示区间 [1, i] 的mex。nt，其中 nt[i] 表示元素 a[i] 下一个出现的位置。线段树：
主处理：
i，计算右端点 j 从 i 到 n 的所有区间的mex之和。a[1]，并找到下一个出现的位置 pos。如果区间 [1, pos-1] 的最大值大于 a[1]，更新相关区间的值。#include#include using namespace std;#define int long longconst int maxm = 2e5 + 5;int nt[maxm];int a[maxm];int b[maxm];int n;struct Tree { int ma[maxm * 2]; int sum[maxm * 2]; int laz[maxm * 2]; inline void push(int node) { if (laz[node] != -1) { int mid = (l + r) / 2; sum[node * 2] = (mid - l + 1) * laz[node]; sum[node * 2 + 1] = (r - mid) * laz[node]; ma[node * 2] = laz[node]; ma[node * 2 + 1] = laz[node]; laz[node * 2] = laz[node]; laz[node * 2 + 1] = laz[node]; laz[node] = -1; } } inline void pop(int node, int l, int r) { if (laz[node] != -1) { int mid = (l + r) / 2; sum[node * 2] = (mid - l + 1) * laz[node]; sum[node * 2 + 1] = (r - mid) * laz[node]; ma[node * 2] = laz[node]; ma[node * 2 + 1] = laz[node]; laz[node] = -1; } } void update(int st, int ed, int val, int l, int r, int node) { if (st <= l && ed >= r) { sum[node] = (r - l + 1) * val; ma[node] = val; laz[node] = val; return; } pop(node, l, r); int mid = (l + r) / 2; if (st <= mid) { update(st, ed, val, l, mid, node * 2); } if (ed > mid) { update(st, ed, val, mid + 1, r, node * 2 + 1); } push(node); } int ask(int st, int ed, int l, int r, int node) { if (st <= l && ed >= r) { return sum[node]; } pop(node, l, r); int mid = (l + r) / 2; int ans = 0; if (st <= mid) { ans += ask(st, ed, l, mid, node * 2); } if (ed > mid) { ans += ask(st, ed, mid + 1, r, node * 2 + 1); } return ans; } int ffind(int val, int l, int r, int node) { if (ma[node] <= val) { return n + 1; } if (l == r) { return l; } pop(node, l, r); int mid = (l + r) / 2; int ans = n + 1; ans = ffind(val, l, mid, node * 2); if (ans == n + 1) { ans = ffind(val, mid + 1, r, node * 2 + 1); } return ans; } void build(int l, int r, int node) { if (l == r) { sum[node] = b[l]; ma[node] = b[l]; return; } int mid = (l + r) / 2; build(l, mid, node * 2); build(mid + 1, r, node * 2 + 1); push(node); }};int main() { ios::sync_with_stdio(0); cin.tie(0); while (cin >> n && n <= 2e5) { for (int i = 1; i <= n; ++i) { cin >> a[i]; } vector mark; for (int i = 1; i <= n; ++i) { mark[a[i]]++; } for (int i = 1; i <= n; ++i) { while (mark[i]) { mark[i]++; } b[i] = mark[i]; } mark.clear(); for (int i = n; i >= 1; --i) { if (mark[a[i]] == 0) { nt[i] = n + 1; } else { nt[i] = mark[a[i]]; } mark[a[i]] = i; } Tree tree; tree.build(1, n, 1); int ans = 0; for (int i = 1; i <= n; ++i) { ans += tree.ask(i, n, 1, n, 1); if (i != n) { int val = a[i]; int pos = nt[i]; int t = tree.ffind(val, 1, n, 1); if (t <= pos - 1) { tree.update(t, pos - 1, val, 1, n, 1); } } } cout << ans << endl; }}
预处理：
b，其中 b[i] 是区间 [1, i] 的mex。nt，记录每个元素的下一个出现位置。线段树：
sum（区间和）、ma（区间最大值）和 laz（懒标记）。update 方法用于区间覆盖。ask 方法用于区间和查询。ffind 方法用于树上二分查找大于某个值的第一个位置。build 方法用于树的构建。主处理：
i，计算右边所有区间的mex之和。转载地址：http://ptkv.baihongyu.com/