程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4358 Boring counting（樹狀數組）

HDU 4358 Boring counting（樹狀數組）

編輯：C++入門知識

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;
}