[JZOJ4680] 自然数 [HDU4747] Mex

Description

Solution

50%

显然，超过 N−1 的数是没有什么用的，所以可以忽略掉。 枚举区间左边界，右边界左边界开始向右扫，维护一个标记数组和答案指针，指针随着标记的更新而增大

O(N2) 轻松解决

100%

我们发现， mex(i,i) 到 mex(i,n) 是单调不减的 先用 50 分的方法跑出 mex(1,1) 到 mex(1,n)

我们可以从左往右删掉当前第一个数，计算剩余区间的影响和答案 就是说，从 mex(1,1) 到 mex(1,n) 得出 mex(2,2) 到 mex(2,n)

删掉第一个数，造成的影响是一个连续的区间（自己YY），这区间内的 mex 都赋为这个数

如果得出了区间的左边界和区间的右边界，就可以很简单的用线段树维护。

由于 mex 的单调性，左边界显然就是第一个 mex 大于它的位置，这个可以在线段树上二分得到

右边界就是下一个序列中等于它的位置（它后面都不会造成影响），可以预处理

于是在 O(NlogN) 复杂度内解决

Code

#include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<cstring> #include<iostream> #define fo(i,a,b) for(i=a;i<=b;i++) #define fod(i,a,b) for(i=a;i>=b;i--) #define N 200005 struct node { long long sm,mx; int ls,rs; }tr[5*N]; using namespace std; int n,a[N],lt[N],b[N],nd; long long lazy[5*N]; bool bz[N]; long long ans; void down(int now,int l,int mid,int r) { int ls=tr[now].ls,rs=tr[now].rs; if (lazy[now]!=-1) { tr[ls].sm=(mid-l+1)*lazy[now]; tr[rs].sm=(r-mid)*lazy[now]; tr[ls].mx=tr[rs].mx=lazy[now]; lazy[ls]=lazy[rs]=lazy[now]; lazy[now]=-1; } } void build(int now,int l,int r) { if(l==r) return; int mid=(l+r)/2; tr[now].ls=++nd; build(nd,l,mid); tr[now].rs=++nd; build(nd,mid+1,r); } void change(int now,int l,int r,int x,int y,int v) { if (x>y) return; if (l==x&&r==y) { tr[now].sm=v*(r-l+1); tr[now].mx=v; lazy[now]=v; return; } int ls=tr[now].ls,rs=tr[now].rs,mid=(l+r)/2; down(now,l,mid,r); if(y<=mid) change(ls,l,mid,x,y,v); else if(x>mid) change(rs,mid+1,r,x,y,v); else { change(ls,l,mid,x,mid,v); change(rs,mid+1,r,mid+1,y,v); } tr[now].sm=tr[ls].sm+tr[rs].sm; tr[now].mx=max(tr[ls].mx,tr[rs].mx); } int find(int now,int l,int r,int x,int y) { if (l==x&&r==y) return tr[now].sm; int ls=tr[now].ls,rs=tr[now].rs,mid=(l+r)/2; long long s; down(now,l,mid,r); if (y<=mid) s=find(ls,l,mid,x,y); else if (x>mid) s=find(rs,mid+1,r,x,y); else s=find(ls,l,mid,x,mid)+find(rs,mid+1,r,mid+1,y); return s; } int query(int now,int l,int r,int v) { if (l==r) { if (tr[now].mx<=v) return l+2; return l; } int ls=tr[now].ls,rs=tr[now].rs,mid=(l+r)/2; down(now,l,mid,r); if (tr[ls].mx>v) return query(ls,l,mid,v); else return query(rs,mid+1,r,v); } int main() { cin>>n; int i,j; nd=1; build(1,1,n); fo(i,1,n) { scanf("%d",&a[i]); if (a[i]>=n) a[i]=n; b[lt[a[i]]]=i; lt[a[i]]=i; } fo(i,1,n) if (b[i]==0) b[i]=n+1; int p=0; ans=0; memset(lazy,255,sizeof(lazy)); fo(j,1,n) { bz[a[j]]=1; while (bz[p]==1) p++; ans+=p; change(1,1,n,j,j,p); } fo(j,1,n-1) { int lp=query(1,1,n,a[j]),rp=b[j]; change(1,1,n,lp,rp-1,a[j]); ans+=find(1,1,n,j+1,n); } cout<<ans; }