LA 5902,Movie collection

 1 #include <iostream>
 2 #include <string.h>
 3 #include <string>
 4 #include <fstream>
 5 #include <algorithm>
 6 #include <stdio.h>
 7 #include <vector>
 8 #include <queue>
 9 #include <set>
10 #include <cmath>
11 using namespace std;
12 const double eps = 1e-8;
13 const double pi=acos(-1.0);
14 const int INF=0x7fffffff;
15 unsigned long long uINF = ~0LL;
16 #define MAXN 200007
17 #define mod 1000000007
18 typedef long long LL;
19 int C[MAXN],hash[MAXN],n,m,T,x,y;
20 int lowbit(int x)
21 {
22     return x&-x;
23 }
24 int sum(int x)
25 {
26     int ret=0;
27     while(x>0)
28     {
29         ret+=C[x];x-=lowbit(x);
30     }
31     return ret;
32 }
33 void add(int x,int d)
34 {
35     while(x<=MAXN){
36     C[x]+=d;x+=lowbit(x);}
37 }
38 void init()
39 {
40     for(int i=1;i<=n;i++)
41     hash[i]=n-i+1;
42     for(int i=1;i<=MAXN;i++)
43     C[i]=lowbit(i);
44 }
45 int main()
46 {
47     scanf("%d",&T);
48     while(T--)
49     {
50         scanf("%d%d",&n,&m);
51         //memset(hash,0,sizeof(hash));
52         //memset(C,0,sizeof(C));
53         init();
54         int temp,N=n;
55         for(int i=1;i<=m;i++)
56         {
57             scanf("%d",&temp);
58             int ans=sum(hash[temp]);
59             if(i!=1)printf(" %d",n-ans);
60             else printf("%d",n-ans);
61 
62             add(hash[temp],-1);
63             hash[temp]=++N;
64         }
65         printf("
");
66     }
67     return 0;
68 }
树状数组~