HDU 4358 Boring counting（树状数组）

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

思路：

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

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

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

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

#include<cstdio>  
#include<cstring>  
#include<cmath>  
#include<cstdlib>  
#include<iostream>  
#include<algorithm>  
#include<vector>  
#include<map>  
#include<queue>  
#include<stack> 
#include<string>
#include<map> 
#include<set>
#define eps 1e-6 
#define LL long long  
#define pii (pair<int, int>)
#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<int> G[maxn];
int vis[maxn], ans[maxn], cnt[maxn];
vector<int> pos[maxn];
map<int, int> 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:\n", ++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\n", 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 <n-1; i++) {
			int u, v;
			scanf("%d%d", &u, &v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		dfs(1);
		cin >> 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 4358 Boring counting（树状数组）

原文：http://blog.csdn.net/u014664226/article/details/47347469