HDU 4358 Boring counting 树状数组+思路

研究了整整一天orz……直接上官方题解神思路

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <vector>

 #include <algorithm>

 using namespace std;

 const int MAXN = ;

 struct node

 {

     int v, next;

 };

 struct subTree

 {

     int st, ed;

 };

 struct Queryy

 {

     int i;

     int st, ed;

 };

 int N, K, Q;

 int EdgeN, TimeFlag;

 node D[MAXN];   //树节点

 int C[MAXN];    //树状数组

 int head[MAXN];

 subTree tree[MAXN];   //子树映射成线性序列之后对应的区间

 Queryy qry[MAXN];     //查询信息

 int weight[MAXN], addr[MAXN];

 int ans[MAXN];

 vector<int> pos[MAXN];

 void AddEdge( int u, int v )

 {

     D[EdgeN].v = v;

     D[EdgeN].next = head[u];

     head[u] = EdgeN++;

     return;

 }

 void DFS( int cur )                    //树形结构转线性结构

 {

     tree[ cur ].st = ++TimeFlag;

     addr[ TimeFlag ] = weight[ cur ];

     for ( int i = head[cur]; i != -; i = D[i].next )

         DFS( D[i].v );

     tree[cur].ed = TimeFlag;

     return;

 }

 int lowbit( int x )

 {

     return (-x) & x;

 }

 void add( int x, int val )

 {

     while ( x <= N )

     {

         C[x] += val;

         x += lowbit(x);

     }

     return;

 }

 int query( int x )

 {

     int res = ;

     while ( x >  )

     {

         res += C[x];

         x -= lowbit(x);

     }

     return res;

 }

 bool cmp( int a, int b )

 {

     return weight[a] < weight[b];

 }

 void init()    //将weight离散化

 {

     sort( addr + , addr + N + , cmp );

     int cnt = , pre = -;

     for ( int i = ; i <= N; ++i )

     {

         if ( weight[ addr[i] ] != pre )

             pre = weight[ addr[i] ], weight[ addr[i] ] = ++cnt;

         else weight[ addr[i] ] = cnt;

     }

     return;

 }

 bool cmp2( Queryy a, Queryy b )

 {

     return a.ed < b.ed;

 }

 void solved()

 {

     for ( int i = ; i <= N; ++i ) pos[i].clear();

     sort( qry, qry + Q, cmp2 );

     int cur = ;

     for ( int i = ; i <= N; ++i )

     {

         int val = addr[i];

         pos[val].push_back(i);

         int sz = pos[val].size();

         if ( sz == K )

             add( pos[val][ sz - K ],  );

         else if ( sz > K )

         {

             add( pos[val][ sz - K ],  );

             add( pos[val][ sz - K -  ], - );

         }

         //printf( "ed = %d\n", qry[cur].ed );

         while ( cur < Q && qry[cur].ed == i )

         {

             int id = qry[cur].i;

             ans[id] = query( qry[cur].ed ) - query( qry[cur].st -  );

           //  printf("ans[%d] = %d\n", id, ans[id] );

             ++cur;

         }

     }

     return;

 }

 int main()

 {

     int T, cas = ;

     scanf( "%d", &T );

     while ( T-- )

     {

         memset( head, -, sizeof( head ) );

         memset( C, , sizeof(C) );

         scanf( "%d%d", &N, &K );

         for ( int i = ; i <= N; ++i )

         {

             scanf( "%d", &weight[i] );

             addr[i] = i;

         }

         init();

         EdgeN = ;

         for ( int i = ; i < N; ++i )      //建树

         {

             int u, v;

             scanf( "%d%d", &u, &v );

             AddEdge( u, v );

         }

         TimeFlag = ;

         DFS();                           //树形结构转线性结构

         scanf( "%d", &Q );

         printf( "Case #%d:\n", ++cas );

         for ( int i = ; i < Q; ++i )

         {

             int u;

             scanf( "%d", &u );

             qry[i].i = i;

             qry[i].st = tree[u].st;

             qry[i].ed = tree[u].ed;

            // printf( "%d %d\n", qry[i].st, qry[i].ed );

         }

         solved();

         for ( int i = ; i < Q; ++i )

             printf( "%d\n", ans[i] );

         if ( T ) puts("");

     }

     return ;

 }