题意：
给出(n)个数，然后求(sum_{i=1}^nsum_{j=i}^nmex(i,j))。(mex(i,j))表示区间([i,j])的(mex)。
思路：
- 考虑枚举左右端点的其中一个，然后快速统计答案。
- 观察发现对于一个(a_i)，如果区间左端点从包含它到了不包含的状态，那么其会影响([i+1,next[a_i]-1])这个区间中的(mex)值。
- 那么尝试枚举左端点，根据左端点数值快速统计答案。（一开始想的右端点半天出不来啊= ，=）
- 怎么统计呢？
- 观察到左端点固定的话，区间(mex)是单调不减的，那么我们就利用这一性质！
- 找到右端点位于([i+1,next[a_i]-1])时，区间(mex)大于(a_i)的集合，然后区间修改即可。
总的来说，主要还是要分析到一个点对区间(mex)的影响，以及区间(mex)的单调性。
#include <bits/stdc++.h>
//#define heyuhhh ok
using namespace std;
typedef long long ll;
const int N = 200005;
int a[N], b[N];
int n;
bool vis[N];
ll sumv[N << 2], lz[N << 2], maxv[N << 2];
int nxt[N];
void Getmex() {
map <int, int> mp;
int j = 0;
for(int i = 0; i <= n + 1; i++) vis[i] = 0;
for(int i = 1; i <= n; i++) {
if(a[i] <= n) vis[a[i]] = 1;
while(vis[j]) ++j;
b[i] = j;
}
for(int i = n; i >= 1; i--) {
if(mp.find(a[i]) == mp.end()) nxt[i] = n + 1;
else nxt[i] = mp[a[i]];
mp[a[i]] = i;
}
}
void push_up(int o) {
sumv[o] = sumv[o << 1] + sumv[o << 1|1];
maxv[o] = max(maxv[o << 1], maxv[o << 1|1]);
}
void push_down(int o, int l, int r) {
if(lz[o] != -1) {
int mid = (l + r) >> 1;
lz[o << 1] = lz[o << 1|1] = lz[o];
sumv[o << 1] = 1ll * (mid - l + 1) * lz[o];
sumv[o << 1|1] = 1ll * (r - mid) * lz[o];
maxv[o << 1] = maxv[o << 1|1] = lz[o];
lz[o] = -1;
}
}
void build(int o, int l, int r) {
lz[o] = -1;
if(l == r) {
sumv[o] = maxv[o] = b[l];
return;
}
int mid = (l + r) >> 1;
build(o << 1, l, mid); build(o << 1|1, mid + 1, r);
push_up(o);
}
int query_l(int o, int l, int r, int L, int R, int v) {
if(l == r) return l;
int mid = (l + r) >> 1;
push_down(o, l, r);
int ok = -1;
if(maxv[o << 1] >= v && L <= mid) ok = query_l(o << 1, l, mid, L, R, v);
if(ok == -1 && maxv[o << 1|1] >= v && R > mid) ok = query_l(o << 1|1, mid + 1, r, L, R, v);
return ok;
}
void update(int o, int l, int r, int L, int R, int v) {
if(L <= l && r <= R) {
lz[o] = v;
sumv[o] = 1ll * (r - l + 1) * v;
maxv[o] = v;
return;
}
push_down(o, l, r);
int mid = (l + r) >> 1;
if(L <= mid) update(o << 1, l, mid, L, R, v);
if(R > mid) update(o << 1|1, mid + 1, r, L, R, v);
push_up(o);
}
ll query(int o, int l, int r, int L, int R) {
if(L <= l && r <= R) {
return sumv[o];
}
push_down(o, l, r);
int mid = (l + r) >> 1;
ll res = 0;
if(L <= mid) res += query(o << 1, l, mid, L, R);
if(R > mid) res += query(o << 1|1, mid + 1, r, L, R);
return res;
}
int main() {
while(cin >> n && n) {
for(int i = 1; i <= n; i++) cin >> a[i];
Getmex();
build(1, 1, n);
ll ans = query(1, 1, n, 1, n);
for(int i = 1; i < n; i++) {
int Next = nxt[i] - 1;
int L = query_l(1, 1, n, i + 1, Next, a[i]);
if(L != -1) update(1, 1, n, L, Next, a[i]);
ans += query(1, 1, n, i + 1, n);
}
cout << ans << '
';
}
return 0;
}