### Brief description:

。。。给定一个长度为 n 的非负数列。。定义 mex(l, r) 为 l，r 区间里最小的没有出现的数字。

。。求所有 mex(l, r) 的和。。。

### Analysis:

..。直接合并区间难以进行时。。利用离线先固定一个端点。。沿着另一个端点扫应该是接下来第一个要想的方法了。。。

。艹。。我是傻逼么。。

。。先 O(n) 搞出 mex1[i] 表示初始的 mex(1, i)。。这个是单调递增的。。。

。。。再 O(n) 搞出每个 nxt[i] 。。表示右边第一个和 i 相同的位置。。（如果没有则等于 n+1。。。。

。。。接着沿着左侧开始删除。。删除前要统计出以这个点为左端点的所有 mex。 。。

。。。考虑删除 a[i]。。那么将 i+1 到 nxt[i]-1 之间。。mex 大于 a[i] 的全设置成 a[i]。即可。。。

。。。于是我们需要维护。。。区间求和。。。以及区间赋值成至多 a[i]。。。这是一个线段树的 Open Problem 。。。（至少对我而言。？。。

。。。进一步分析发现 mex 始终是单调递增的。。

。。。因此将 i+1 到 nxt[i]-1 赋值到至多 a[i]。。就是将第一个大于 a[i] 的位置 到 nxt[i] -1 赋值到 a[i] 即可。。而这是一个线段树入门级别的操作。。。

const int N = 200009, NN = 4*N; int A[N], C[N], nxt[N], mex1[N]; int n; LL ss[NN]; int mx[NN]; bool dd[NN]; int a, b, c; #define root 1, 1, n #define lx (x << 1) #define rx (lx | 1) #define ml (l + r >> 1) #define mr (ml + 1) #define len (r - l + 1) #define xc x, l, r #define lc lx, l, ml #define rc rx, mr, r inline void Apply_Cov(int x, int l, int r, int val){ mx[x] = val, ss[x] = (LL) len * val, dd[x] = 1; } void Release(int x, int l, int r){ if (dd[x]){ Apply_Cov(lc, mx[x]), Apply_Cov(rc, mx[x]); dd[x] = 0; } } void Update(int x){ mx[x] = max(mx[lx], mx[rx]); ss[x] = ss[lx] + ss[rx]; } void Insert(int x, int l, int r){ if (b < l || r < a) return; if (a <= l && r <= b){ Apply_Cov(xc, c); } else{ Release(xc); Insert(lc), Insert(rc); Update(x); } } int Upper_Bound(int x, int l, int r){ if (l == r) return l; else{ Release(xc); return mx[lx] > c ? Upper_Bound(lc) : Upper_Bound(rc); } } void Build(int x, int l, int r){ dd[x] = 0; if (l == r) mx[x] = ss[x] = mex1[l]; else Build(lc), Build(rc), Update(x); } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif while (RD(n)){ REP_1_C(i, n) checkMin(RD(A[i]), 200001); int mex = 0; RST(C); REP_1(i, n){ ++C[A[i]]; while (C[mex]) ++mex; mex1[i] = mex; } fill(C, C+N, n+1); DWN_1(i, n, 1){ nxt[i] = C[A[i]]; C[A[i]] = i; } LL res = 0; Build(root); REP_1(i, n){ res += ss[1]; if (mx[1] > A[i]){ c = A[i], a = Upper_Bound(root), b = nxt[i]-1; if (a <= b) Insert(root); } a = i, b = i, c = 0, Insert(root); if (!mx[1]) break; } OT(res); } }