HDU 4358 Boring counting 树状数组+思路

研究了整整一天orz……直接上官方题解神思路
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <vector>
  5 #include <algorithm>
  6 
  7 using namespace std;
  8 
  9 const int MAXN = 100100;
 10 
 11 struct node
 12 {
 13     int v, next;
 14 };
 15 
 16 struct subTree
 17 {
 18     int st, ed;
 19 };
 20 
 21 struct Queryy
 22 {
 23     int i;
 24     int st, ed;
 25 };
 26 
 27 int N, K, Q;
 28 int EdgeN, TimeFlag;
 29 node D[MAXN];   //树节点
 30 int C[MAXN];    //树状数组
 31 int head[MAXN];
 32 subTree tree[MAXN];   //子树映射成线性序列之后对应的区间
 33 Queryy qry[MAXN];     //查询信息
 34 int weight[MAXN], addr[MAXN];
 35 int ans[MAXN];
 36 vector<int> pos[MAXN];
 37 
 38 void AddEdge( int u, int v )
 39 {
 40     D[EdgeN].v = v;
 41     D[EdgeN].next = head[u];
 42     head[u] = EdgeN++;
 43     return;
 44 }
 45 
 46 void DFS( int cur )                    //树形结构转线性结构
 47 {
 48     tree[ cur ].st = ++TimeFlag;
 49     addr[ TimeFlag ] = weight[ cur ];
 50     for ( int i = head[cur]; i != -1; i = D[i].next )
 51         DFS( D[i].v );
 52     tree[cur].ed = TimeFlag;
 53     return;
 54 }
 55 
 56 int lowbit( int x )
 57 {
 58     return (-x) & x;
 59 }
 60 
 61 void add( int x, int val )
 62 {
 63     while ( x <= N )
 64     {
 65         C[x] += val;
 66         x += lowbit(x);
 67     }
 68     return;
 69 }
 70 
 71 int query( int x )
 72 {
 73     int res = 0;
 74     while ( x > 0 )
 75     {
 76         res += C[x];
 77         x -= lowbit(x);
 78     }
 79     return res;
 80 }
 81 
 82 bool cmp( int a, int b )
 83 {
 84     return weight[a] < weight[b];
 85 }
 86 
 87 void init()    //将weight离散化
 88 {
 89     sort( addr + 1, addr + N + 1, cmp );
 90 
 91     int cnt = 0, pre = -1;
 92     for ( int i = 1; i <= N; ++i )
 93     {
 94         if ( weight[ addr[i] ] != pre )
 95             pre = weight[ addr[i] ], weight[ addr[i] ] = ++cnt;
 96         else weight[ addr[i] ] = cnt;
 97     }
 98     return;
 99 }
100 
101 bool cmp2( Queryy a, Queryy b )
102 {
103     return a.ed < b.ed;
104 }
105 
106 void solved()
107 {
108     for ( int i = 0; i <= N; ++i ) pos[i].clear();
109 
110     sort( qry, qry + Q, cmp2 );
111     int cur = 0;
112     for ( int i = 1; i <= N; ++i )
113     {
114         int val = addr[i];
115         pos[val].push_back(i);
116         int sz = pos[val].size();
117         if ( sz == K )
118             add( pos[val][ sz - K ], 1 );
119         else if ( sz > K )
120         {
121             add( pos[val][ sz - K ], 1 );
122             add( pos[val][ sz - K - 1 ], -2 );
123         }
124         //printf( "ed = %d
", qry[cur].ed );
125         while ( cur < Q && qry[cur].ed == i )
126         {
127             int id = qry[cur].i;
128             ans[id] = query( qry[cur].ed ) - query( qry[cur].st - 1 );
129           //  printf("ans[%d] = %d
", id, ans[id] );
130             ++cur;
131         }
132     }
133     return;
134 }
135 
136 int main()
137 {
138     int T, cas = 0;
139     scanf( "%d", &T );
140     while ( T-- )
141     {
142         memset( head, -1, sizeof( head ) );
143         memset( C, 0, sizeof(C) );
144 
145         scanf( "%d%d", &N, &K );
146         for ( int i = 1; i <= N; ++i )
147         {
148             scanf( "%d", &weight[i] );
149             addr[i] = i;
150         }
151         init();
152 
153         EdgeN = 0;
154 
155         for ( int i = 1; i < N; ++i )      //建树
156         {
157             int u, v;
158             scanf( "%d%d", &u, &v );
159             AddEdge( u, v );
160         }
161 
162         TimeFlag = 0;
163         DFS(1);                           //树形结构转线性结构
164 
165         scanf( "%d", &Q );
166         printf( "Case #%d:
", ++cas );
167         for ( int i = 0; i < Q; ++i )
168         {
169             int u;
170             scanf( "%d", &u );
171             qry[i].i = i;
172             qry[i].st = tree[u].st;
173             qry[i].ed = tree[u].ed;
174            // printf( "%d %d
", qry[i].st, qry[i].ed );
175         }
176         solved();
177         for ( int i = 0; i < Q; ++i )
178             printf( "%d
", ans[i] );
179 
180         if ( T ) puts("");
181     }
182     return 0;
183 }