hdu 4747 Mex （线段树lazy标记）
题意：给出n(n<=200000)个数，问所有区间[l,r]中mex的和。 （一个区间mex的定义为，这个区间中没有出现的最小的非负数）
思路：我们观察到mex(1,i)随着i增大，是不减的。(单调是线段树查询区间的时候非常好用的东西,这也是次题的突破口)
mex(1,i)可以O(n)维护出
现在我们考虑左端点向右移动对答案的影响。
当i移动到i+1时，此时序列中少了a[i]，设r为最小的x，满足a[x]=a[i]，那么当右断点在区间[r+1,n]，mex值是没有改变的。
当右端点属于[i+1,r-1]时，mex大于a[i]的会变成a[i]。
由于我们知道从1到某区间的mex值是单调的，那么mex大于a[i]的点必然是连续的一段。
我们可以知道最左边的q，满足mex(1,q)大于a[i]，然后将区间[q,r-1]成段更新为a[i]
因此整理思路，我们需要做两件事。
一个是每次区间求和，一个是找到最左边的q满足mex(1,q)大于a[i].
线段树维护三个域，max域，表示该区间中mex(1,i)的最大值；
sum域，表示该区间中mex(1,i)的和
lazy域，表示延迟标记。
可以预处理出nxt数组，表示位置i上的数下次出现最近是在nxt[i]
1#include <cstdio>
2#include <cstring>
3#include <algorithm>
4#include <iostream>
5#include <set>
6using namespace std;
7const int N=2E5+7;
8#define lson l,m,rt<<1
9#define rson m+1,r,rt<<1|1
10typedef long long LL;
11int n;
12int a[N];
13bool vis[N];
14int Mex[N];
15pair < int , int > b[N];
16int nxt[N];
1struct Tree
2{
3 LL lazy;
4 LL sum;
5 LL mx;
6}tree[N<<2];
7void PushUp( int rt)
8{
9 tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
10 tree[rt].mx = max(tree[rt<<1].mx,tree[rt<<1|1].mx);
11}
12void PushDown( int l,int r,int rt)
13{
14 if (tree[rt].lazy!=-1)
15 {
16 int m = (l+r)>>1;
17 tree[rt<<1].sum = (m+1-l)*tree[rt].lazy;
18 tree[rt<<1|1].sum = (r-m)*tree[rt].lazy;
19 tree[rt<<1].lazy = tree[rt<<1|1].lazy = tree[rt<<1].mx = tree[rt<<1|1].mx = tree[rt].lazy;
20 tree[rt].lazy = -1;
1 }
2}
3void update( int L,int R,int sc,int l,int r,int rt)
4{
5 if (L<=l&&r<=R)
6 {
7 tree[rt].sum = (r-l+1)*sc;
8 tree[rt].lazy = tree[rt].mx =sc;
9 return;
10 }
11 PushDown(l,r,rt);
12 int m = (l+r)>>1;
13 if (L<=m) update(L,R,sc,lson);
14 if (R>=m+1) update(L,R,sc,rson);
15 PushUp(rt);
16}
17int queryP(int x,int l,int r,int rt)
18{
19 if (tree[rt].mx<=x) return r+1;
20 if (l==r) return l;
1 PushDown(l,r,rt);
2 int m = (l+r)>>1;
3 if (tree[rt<<1].mx>x) return queryP(x,lson);
4 else return queryP(x,rson); //先找左边，目的是找到最前面的.
5}
6int main()
7{
1 while (~scanf("%d",&n)&&n)
2 {
3 for ( int i = 1 ;i <= n ; i++)
4 {
5 scanf("%d",&a[i]);
6 // if (a[i]>200000) a[i] = 200001;
7 b[i] = make_pair(a[i],i);
8 nxt[i] = n+1;
9 }
10 sort(b+1,b+n+1);
11 b[n+1].first = b[n].first;
12 b[n+1].second = n+1;
13 for ( int i = 1 ; i <=n ; i++)
14 if (b[i].first == b[i+1].first) nxt[b[i].second] = b[i+1].second;
15 memset(tree,0,sizeof(tree));
16 memset(vis,false,sizeof(vis));
1 int tmp = 0 ;
2 set<int>se;
3 for ( int i = 1 ; i <= n ; i++)
4 {
5 se.insert(a[i]);
6 while (se.find(tmp)!=se.end()) tmp++;
7 update(i,i,tmp,1,n,1);
8 }
9 LL ans = tree[1].sum;
10 for ( int l = 1 ;l <= n ; l++)
11 {
12 update(l,l,0,1,n,1);
13 int pos = queryP(a[l],1,n,1);//找到最左的r满足mex[r]>a[l]
14 pos = max(l+1,pos);//该位置必须还没有被删除，维护下边界。
15 update(pos,nxt[l]-1,a[l],1,n,1);
16 ans += tree[1].sum;
17 }
18 cout<<ans<<endl;
}
}