UVA 1513 Movie collection

时间:2021-11-25 13:32:26
 #include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 200010
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 int sum[N<<],tag[N/];
int n,q,cnt; void PushUp(int rt)
{
sum[rt]=sum[rt<<]+sum[rt<<|];
} void build(int l,int r,int rt)
{
if(l==r)
{
if((l>=N-n)&&l<N)
sum[rt]=,tag[++cnt]=l;
return;
}
int m=(l+r)>>;
build(lson);
build(rson);
PushUp(rt);
} void update(int i,int c,int l,int r,int rt)
{
if(l==r)
{
sum[rt]=c;
return;
}
int m=(l+r)>>;
if(tag[i]<=m)
update(i,c,lson);
else update(i,c,rson);
PushUp(rt);
} int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r)
return sum[rt];
int m=(l+r)>>;
int res=;
if(L<=m)
res+=query(L,R,lson);
if(R>m)
res+=query(L,R,rson);
return res;
} int main(void)
{
int T,x;
scanf("%d",&T);
while(T--)
{
memset(sum,,sizeof(sum));
memset(tag,,sizeof(tag));
int pre;
scanf("%d%d",&n,&q);
cnt=;
build(,N-,);
pre=tag[];
while(q--)
{
scanf("%d",&x);
int ans=;
if(pre<=tag[x]-)
{ update(x,,,N-,);
ans=query(pre,tag[x]-,,N-,),tag[x]=--pre,update(x,,,N-,);}
printf("%d%c",ans,!q?'\n':' ');
}
}
return ;
}