# hdu 4747 Mex （线段树lazy标记）

Posted by 111qqz on Sunday, November 13, 2016

## TOC

mex(1,i)可以O(n)维护出

sum域，表示该区间中mex(1,i)的和

lazy域，表示延迟标记。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
const int N=2E5+7;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long LL;
int  n;
int a[N];
bool vis[N];
int Mex[N];
pair < int , int > b[N];
int nxt[N];

struct Tree
{
LL lazy;
LL sum;
LL mx;
}tree[N<<2];
void PushUp( int rt)
{
tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
tree[rt].mx = max(tree[rt<<1].mx,tree[rt<<1|1].mx);
}
void PushDown( int l,int r,int rt)
{
if (tree[rt].lazy!=-1)
{
int m = (l+r)>>1;
tree[rt<<1].sum = (m+1-l)*tree[rt].lazy;
tree[rt<<1|1].sum = (r-m)*tree[rt].lazy;
tree[rt<<1].lazy = tree[rt<<1|1].lazy = tree[rt<<1].mx = tree[rt<<1|1].mx = tree[rt].lazy;
tree[rt].lazy = -1;

}
}
void update( int L,int R,int sc,int l,int r,int rt)
{
if (L<=l&&r<=R)
{
tree[rt].sum = (r-l+1)*sc;
tree[rt].lazy = tree[rt].mx =sc;
return;
}
PushDown(l,r,rt);
int m = (l+r)>>1;
if (L<=m) update(L,R,sc,lson);
if (R>=m+1) update(L,R,sc,rson);
PushUp(rt);
}
int queryP(int x,int l,int r,int rt)
{
if (tree[rt].mx<=x) return r+1;
if (l==r) return l;

PushDown(l,r,rt);
int m = (l+r)>>1;
if (tree[rt<<1].mx>x) return queryP(x,lson);
else return queryP(x,rson); //先找左边，目的是找到最前面的.
}
int main()
{

while (~scanf("%d",&n)&&n)
{
for ( int i = 1 ;i  <= n ; i++)
{
scanf("%d",&a[i]);
//  if (a[i]>200000) a[i] = 200001;
b[i] = make_pair(a[i],i);
nxt[i] = n+1;
}
sort(b+1,b+n+1);
b[n+1].first = b[n].first;
b[n+1].second = n+1;
for ( int i = 1 ; i <=n ; i++)
if (b[i].first == b[i+1].first) nxt[b[i].second] = b[i+1].second;
memset(tree,0,sizeof(tree));
memset(vis,false,sizeof(vis));

int tmp = 0 ;
set<int>se;
for ( int i = 1 ; i <= n ; i++)
{
se.insert(a[i]);
while (se.find(tmp)!=se.end()) tmp++;
update(i,i,tmp,1,n,1);
}
LL ans = tree[1].sum;
for ( int l =  1 ;l <= n ; l++)
{
update(l,l,0,1,n,1);
int pos = queryP(a[l],1,n,1);//找到最左的r满足mex[r]>a[l]
pos = max(l+1,pos);//该位置必须还没有被删除，维护下边界。
update(pos,nxt[l]-1,a[l],1,n,1);
ans += tree[1].sum;
}
cout<<ans<<endl;

}
}