HDU 4358 Boring counting（树状数组） - c++编程基础

TOP

HDU 4358 Boring counting（树状数组）

2015-11-21 00:55:48 【大中小】浏览:3833次

Tags：HDU 4358 Boring counting

题意：

给定一棵树，每个节点有一个点权，然后有一些询问，求以某个点为根的子树中有多少的数出现了恰好k次。

思路：

首先dfs一次将树形结构转化成线性结构，利用时间戳记录下以结点u为根的子树在数组中的开始位置和结束位置。

那么我们将所有查询记录下来离线来做，将所有的查询按右端点升序排序。

考虑用树状数组来做这道题，每个位置记录当前从1到当前位置有多少数出现了恰好k次。

从头遍历一遍数组，map离散化记录每个值出现的位置，对于每个位置，如果值出现的次数t大于k，那么在将第t-k次出现的位置加一，第t-k-1次出现的位置减二，如果在当前位置与某个查询的r相同，记录答案sum（r）-sum（l-1）

#include
  
     
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
              #include
              
                #define eps 1e-6 #define LL long long #define pii (pair
               
                ) #pragma comment(linker, /STACK:1024000000,1024000000) using namespace std; const int maxn = 100000 + 50; //const int INF = 0x3f3f3f3f; int n, k, q, clock_cnt, dis, kase; int w[maxn], tim[maxn][2], a[maxn]; vector
                
                  G[maxn]; int vis[maxn], ans[maxn], cnt[maxn]; vector
                 
                   pos[maxn]; map
                  
                    trans; int C[maxn]; int lowbit(int x) { return (x&(-x)); } int sumv(int x) { int ret = 0; while(x > 0) { ret += C[x]; x -= lowbit(x); } return ret; } void add(int x, int d) { while(x <= n) { C[x] += d; x += lowbit(x); } } void init() { for(int i = 1; i <= n; i++) { G[i].clear(); pos[i].clear(); } trans.clear(); clock_cnt = 0; dis = 0; //离散化 memset(cnt, 0, sizeof(cnt)); memset(tim, 0, sizeof(tim)); memset(vis, 0, sizeof(vis)); memset(C, 0, sizeof(C)); } int Hash(int t) { if(!trans.count(t)) return trans[t] = ++dis; return trans[t]; } void dfs(int u) { tim[u][0] = ++clock_cnt; a[clock_cnt] = w[u]; vis[u] = 1; int sz = G[u].size(); for(int i = 0; i < sz; i++) { int v = G[u][i]; if(vis[v]) continue; dfs(v); } tim[u][1] = clock_cnt; } struct Query { int l, r, id; bool operator < (const Query A) const { return r < A.r; } } query[maxn]; void solve() { if(kase) cout << endl; printf(Case #%d: , ++kase); int cur = 0; for(int i = 1; i <= n; i++) { cnt[Hash(a[i])]++; pos[Hash(a[i])].push_back(i); if(cnt[Hash(a[i])] >= k) { add(pos[Hash(a[i])][cnt[Hash(a[i])]-k], 1); if(cnt[Hash(a[i])] > k) add(pos[Hash(a[i])][cnt[Hash(a[i])]-k-1], -2); } while(cur < q && query[cur].r == i) { ans[query[cur].id] = sumv(query[cur].r)-sumv(query[cur].l-1); cur++; } } for(int i = 0; i < q; i++) printf(%d , ans[i]); //cout << dis << endl; //for(int i = 1; i <= dis; i++) cout << cnt[i] << endl; } int main() { // freopen(input.txt, r, stdin); int T; cin >> T; while(T--) { init(); scanf(%d%d, &n, &k); for(int i = 1; i <= n; i++) scanf(%d, &w[i]); for(int i = 0; i 
                   
                    > q; for(int i = 0; i < q; i++) { int t; scanf(%d, &t); query[i].l = tim[t][0]; query[i].r = tim[t][1]; query[i].id = i; } sort(query, query+q); // for(int i = 0; i < q; i++) cout << query[i].l << << query[i].r << endl; // cout << clock_cnt << endl; // for(int i = 1; i <= clock_cnt; i++) cout << a[i] << endl; solve(); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】

上一篇：HDU 5352 MZL's City(最小费..	下一篇：poj1228 Grandpa's Estate 凸..