UVA 1513 Movie collection

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #define N 200010
 5 #define lson l,m,rt<<1
 6 #define rson m+1,r,rt<<1|1
 7 
 8 int sum[N<<4],tag[N/2];
 9 int n,q,cnt;
10 
11 void PushUp(int rt)
12 {
13     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
14 }
15 
16 void build(int l,int r,int rt)
17 {
18     if(l==r)
19     {
20         if((l>=N-n)&&l<N)
21             sum[rt]=1,tag[++cnt]=l;
22         return;
23     }
24     int m=(l+r)>>1;
25     build(lson);
26     build(rson);
27     PushUp(rt);
28 }
29 
30 void update(int i,int c,int l,int r,int rt)
31 {
32     if(l==r)
33     {
34         sum[rt]=c;
35         return;
36     }
37     int m=(l+r)>>1;
38     if(tag[i]<=m)
39         update(i,c,lson);
40     else update(i,c,rson);
41     PushUp(rt);
42 }
43 
44 int query(int L,int R,int l,int r,int rt)
45 {
46     if(L<=l&&R>=r)
47         return sum[rt];
48     int m=(l+r)>>1;
49     int res=0;
50     if(L<=m)
51         res+=query(L,R,lson);
52     if(R>m)
53         res+=query(L,R,rson);
54     return res;
55 }
56 
57 int main(void)
58 {
59     int T,x;
60     scanf("%d",&T);
61     while(T--)
62     {
63         memset(sum,0,sizeof(sum));
64         memset(tag,0,sizeof(tag));
65         int pre;
66         scanf("%d%d",&n,&q);
67         cnt=0;
68         build(1,N-1,1);
69         pre=tag[1];
70         while(q--)
71         {
72             scanf("%d",&x);
73             int ans=0;
74             if(pre<=tag[x]-1)
75                 { update(x,0,1,N-1,1);
76                     ans=query(pre,tag[x]-1,1,N-1,1),tag[x]=--pre,update(x,1,1,N-1,1);}
77             printf("%d%c",ans,!q?'
':' ');
78         }
79     }
80     return 0;
81 }