TVP

# HDU 4747 Mex「建议收藏」

2020

``````#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
typedef __int64 ll;
#define N 201000
#define L(x) (x<<1)
#define R(x) ((x<<1)|1)

struct node
{
int l,r,val,lazy;
ll sum;
}tree[N*4];
int a[N],mex[N],next[N];
int n,l,r;
map<int,int> mp;
ll ans;

void up(int i)
{
tree[i].val=max(tree[L(i)].val,tree[R(i)].val);
tree[i].sum=tree[L(i)].sum+tree[R(i)].sum;
}

void down(int i)
{
if(tree[i].lazy!=-1)
{
tree[L(i)].lazy=tree[i].lazy;
tree[L(i)].val=tree[i].lazy;
tree[L(i)].sum=(tree[L(i)].r-tree[L(i)].l+1)*tree[i].lazy;
tree[R(i)].lazy=tree[i].lazy;
tree[R(i)].val=tree[i].lazy;
tree[R(i)].sum=(tree[R(i)].r-tree[R(i)].l+1)*tree[i].lazy;
tree[i].lazy=-1;
}
}

void init(int l,int r,int i)
{
tree[i].l=l; tree[i].r=r; tree[i].lazy=-1;
if(l==r)
{
tree[i].val=mex[l];
tree[i].sum=mex[l];
return ;
}
int mid=(l+r)>>1;
init(l,mid,L(i));
init(mid+1,r,R(i));
up(i);
}

void update(int l,int r,int i,int k)
{
if(l==tree[i].l&&r==tree[i].r)
{
tree[i].sum=(tree[i].r-tree[i].l+1)*k;
tree[i].val=k;
tree[i].lazy=k;
return ;
}
down(i);
int mid=(tree[i].l+tree[i].r)>>1;
if(r<=mid) update(l,r,L(i),k);
else if(l>mid) update(l,r,R(i),k);
else
{
update(l,mid,L(i),k);
update(mid+1,r,R(i),k);
}
up(i);
}

void query(int i,int k)
{
if(tree[i].l==tree[i].r)
{
if(tree[i].val>k) l=tree[i].l;
else l=n+1;
return ;
}
down(i);
if(tree[L(i)].val>k) query(L(i),k);
else query(R(i),k);
up(i);
}

int main()
{
int i,j;
while(~scanf("%d",&n))
{
if(!n) break;
mp.clear(); // get mex
j=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
mp[a[i]]=1;
while(mp[j]) j++;
mex[i]=j;
}
mp.clear(); // get next
for(i=1;i<=n;i++) mp[a[i]]=n+1;
for(i=n;i>=1;i--)
{
next[i]=mp[a[i]];
mp[a[i]]=i;
}
//for(i=1;i<=n;i++) printf("%d %d\n",mex[i],next[i]);
init(1,n,1);
for(i=1,ans=0;i<=n;i++)
{
ans+=tree[1].sum;
query(1,a[i]);
r=next[i];
//printf("%d %d\n",l,r);
if(l<r)
{
update(l,r-1,1,a[i]);
}
update(i,i,1,0);
}
printf("%I64d\n",ans);
}
return 0;
}``````

0 条评论

LV.