HDU 4747 Mex【线段树上二分+扫描线】

【题意概述】

　　一个区间的Mex为这个区间没有出现过的最小自然数，现在给你一个序列，要求求出所有区间的Mex的和。

【题解】

　　扫描线+线段树。

　　我们在线段树上维护从当前左端点开始的前缀Mex，显然从左到右Mex单调上升。

　　然后我们把区间左端点逐渐向右边移动，也就是扫描线是左端点。

　　我们可以发现每次移动的影响就是 [这个数的位置, 这个数下一次出现的位置) 这个区间内大于这个数的Mex全部变为这个数。

　　那么我们在线段树上二分出第一个大于等于Mex的位置，然后区间修改即可。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 #define rg register

 #define N 200010

 #define ls (u<<1)

 #define rs (u<<1|1)

 #define mid ((a[u].l+a[u].r)>>1)

 using namespace std;

 int n,m,v[N],b[N],c[N],nxt[N],pos[N],mex[N];

 LL ans,u[N];

 struct tree{int l,r,nl,nr; LL sum; bool tag;}a[N<<];

 inline int read(){

     int k=,f=; char c=getchar();

     while(c<''||c>'')c=='-'&&(f=-),c=getchar();

     while(''<=c&&c<='')k=k*+c-'',c=getchar();

     return k*f;

 }

 void build(int u,int l,int r){

     a[u].l=l; a[u].r=r; a[u].tag=;

     if(l<r){

         build(ls,l,mid); build(rs,mid+,r);

         a[u].sum=a[ls].sum+a[rs].sum; a[u].nl=a[ls].nl,a[u].nr=a[rs].nr;

     }

     else a[u].sum=a[u].nl=a[u].nr=mex[l];

 }

 inline void pushdown(int u){

     a[ls].tag=a[rs].tag=;

     a[ls].nl=a[ls].nr=a[rs].nl=a[rs].nr=a[u].nl;

     a[ls].sum=(a[ls].r-a[ls].l+)*a[ls].nl;

     a[rs].sum=(a[rs].r-a[rs].l+)*a[rs].nl;

     a[u].tag=;

 }

 void update(int u,int l,int r,int num){

     if(l<=a[u].l&&a[u].r<=r&&a[u].nl>num){

         a[u].tag=; a[u].nl=a[u].nr=num; a[u].sum=(a[u].r-a[u].l+)*num;

         return;

     }

     if(a[u].nr<=num) return;

     if(a[u].tag) pushdown(u);

     if(a[ls].nr>num&&l<=mid) update(ls,l,r,num);

     if(r>mid) update(rs,l,r,num);

     a[u].sum=a[ls].sum+a[rs].sum; a[u].nl=a[ls].nl,a[u].nr=a[rs].nr;

 }

 LL query(int u,int l,int r){

     if(l<=a[u].l&&a[u].r<=r) return a[u].sum;

     if(a[u].tag) pushdown(u); LL ret=;

     if(l<=mid) ret+=query(ls,l,r);

     if(r>mid) ret+=query(rs,l,r);

     return ret;

 }

 inline void Pre(){

     ans=;

     memset(pos,,sizeof(pos));

     memset(u,,sizeof(u));

 }

 int main(){

     while(){

         n=read(); if(!n) break;

         Pre();

         for(rg int i=;i<=n;i++) v[i]=b[i]=read();

         sort(b+,b++n); m=unique(b+,b++n)-b-;

         for(rg int i=;i<=n;i++) c[i]=lower_bound(b+,b++m,v[i])-b;

 //        for(rg int i=1;i<=n;i++) printf("%d ",c[i]); puts("c");

         for(rg int i=n;i;i--) nxt[i]=(pos[c[i]])?pos[c[i]]:n+,pos[c[i]]=i;

 //        for(rg int i=1;i<=n;i++) printf("%d ",nxt[i]); puts("");

         int now=;

         for(rg int i=;i<=n;i++){

             if(v[i]<=n) u[v[i]]=;

             while(u[now]) now++;

             ans+=(mex[i]=now);

         }

 //        for(rg int i=1;i<=n;i++) printf("%d ",mex[i]);

 //        printf("ans=%lld\n",ans);

         build(,,n);

         for(rg int i=;i<=n;i++){

             update(,i+,nxt[i]-,v[i]);

             ans+=query(,i+,n);

 //            printf("ans=%lld\n",ans);

         }

         printf("%lld\n",ans);

     }

     return ;

 }