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];
17
18struct Tree
19{
20 LL lazy;
21 LL sum;
22 LL mx;
23}tree[N<<2];
24void PushUp( int rt)
25{
26 tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
27 tree[rt].mx = max(tree[rt<<1].mx,tree[rt<<1|1].mx);
28}
29void PushDown( int l,int r,int rt)
30{
31 if (tree[rt].lazy!=-1)
32 {
33 int m = (l+r)>>1;
34 tree[rt<<1].sum = (m+1-l)*tree[rt].lazy;
35 tree[rt<<1|1].sum = (r-m)*tree[rt].lazy;
36 tree[rt<<1].lazy = tree[rt<<1|1].lazy = tree[rt<<1].mx = tree[rt<<1|1].mx = tree[rt].lazy;
37 tree[rt].lazy = -1;
38
39 }
40}
41void update( int L,int R,int sc,int l,int r,int rt)
42{
43 if (L<=l&&r<=R)
44 {
45 tree[rt].sum = (r-l+1)*sc;
46 tree[rt].lazy = tree[rt].mx =sc;
47 return;
48 }
49 PushDown(l,r,rt);
50 int m = (l+r)>>1;
51 if (L<=m) update(L,R,sc,lson);
52 if (R>=m+1) update(L,R,sc,rson);
53 PushUp(rt);
54}
55int queryP(int x,int l,int r,int rt)
56{
57 if (tree[rt].mx<=x) return r+1;
58 if (l==r) return l;
59
60 PushDown(l,r,rt);
61 int m = (l+r)>>1;
62 if (tree[rt<<1].mx>x) return queryP(x,lson);
63 else return queryP(x,rson); //先找左边，目的是找到最前面的.
64}
65int main()
66{
67
68 while (~scanf("%d",&n)&&n)
69 {
70 for ( int i = 1 ;i <= n ; i++)
71 {
72 scanf("%d",&a[i]);
73 // if (a[i]>200000) a[i] = 200001;
74 b[i] = make_pair(a[i],i);
75 nxt[i] = n+1;
76 }
77 sort(b+1,b+n+1);
78 b[n+1].first = b[n].first;
79 b[n+1].second = n+1;
80 for ( int i = 1 ; i <=n ; i++)
81 if (b[i].first == b[i+1].first) nxt[b[i].second] = b[i+1].second;
82 memset(tree,0,sizeof(tree));
83 memset(vis,false,sizeof(vis));
84
85
86 int tmp = 0 ;
87 set<int>se;
88 for ( int i = 1 ; i <= n ; i++)
89 {
90 se.insert(a[i]);
91 while (se.find(tmp)!=se.end()) tmp++;
92 update(i,i,tmp,1,n,1);
93 }
94 LL ans = tree[1].sum;
95 for ( int l = 1 ;l <= n ; l++)
96 {
97 update(l,l,0,1,n,1);
98 int pos = queryP(a[l],1,n,1);//找到最左的r满足mex[r]>a[l]
99 pos = max(l+1,pos);//该位置必须还没有被删除，维护下边界。
100 update(pos,nxt[l]-1,a[l],1,n,1);
101 ans += tree[1].sum;
102 }
103 cout<<ans<<endl;
104
105
106
107 }
108}