fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e5 + 5; 
  12. const int Q = 1e5 + 5; 
  13. const int B = 316; // sqrt(N) 
  14.  
  15. // - Bài toán này có thể giải quyết bằng Thuật toán Mo, kèm với Fenwick Tree
  16. //   Độ phức tạp: O((N + Q) * sqrt(N) * log2(N)) với B = sqrt(N)
  17. // - Tuy vẫn đủ để pass nhưng ở đây ta có thể đưa ra nhận xét để không cần phải dùng đến Fenwick Tree
  18. // - Nhận xét: 
  19. //   + Bản chất của Fenwick Tree là prefix/suffix sum, trong bài này thì là suffix sum
  20. //   + Khi ta thay đổi giá trị tại vị trí pos thì suf[1..pos] cũng sẽ bị thay đổi theo (*)
  21. //   + Còn với thuật toán Mo thì điểm đặc biệt là ở mỗi bước, con trỏ cur_l hoặc cur_r chỉ dịch 1 đơn vị
  22. //     dẫn đến giá trị cnt[c] sẽ chỉ tăng hoặc giảm 1 đơn vị
  23. //   + Xét trường hợp cnt[c] -> cnt[c] + 1: 
  24. //     theo (*) thì sẽ tương ứng với 2 thao tác là giảm đoạn suf[1..cnt[c]] đi 1 đơn vị, và tăng đoạn suf[1..cnt[c] + 1] lên 1 đơn vị
  25. //     => Sau 2 thao tác thì đơn giản chỉ là tăng suf[cnt[c] + 1] lên 1 đơn vị
  26. //   + Trường hợp cnt[c] -> cnt[c] - 1 hoàn toàn tương tự: sau 2 thao tác thì đơn giản chỉ là giảm suf[cnt[c]] đi 1 đơn vị       
  27. // => Do đó ta không cần dùng đến Fenwick Tree mà chỉ cần một mảng suf[] bình thường
  28. // => Độ phức tạp O((N + Q) * sqrt(N)) với B = sqrt(N)
  29.  
  30. struct Query {
  31. 	int l, r, k, idx;  
  32. 	bool operator<(const Query &other) const {
  33. 		if (l / B == other.l / B) {
  34. 			return (l / B & 1) ? (r > other.r) : (r < other.r); 
  35. 		}
  36. 		return (l < other.l); 
  37. 	}
  38. }; 
  39.  
  40. int n, q; 
  41. int c[N]; 
  42. vector<int> adj[N]; 
  43. vector<Query> queries;  
  44.  
  45. int euler_tour[N];
  46. int tin[N], tout[N], timer;  
  47.  
  48. void dfs(int u, int p) {
  49. 	tin[u] = ++timer;  
  50. 	euler_tour[timer] = u; 
  51. 	for (int v : adj[u]) {
  52. 		if (v == p) continue; 
  53. 		dfs(v, u); 
  54. 	}
  55. 	tout[u] = timer;  
  56. }
  57.  
  58. int cnt[N]; // cnt[c] = Số lần xuất hiện của màu c
  59. int suf[N]; // suf[i] = Tổng đoạn [i, n] = Số lượng màu c sao cho cnt[c] >= i 
  60. int ans[Q]; // ans[i] = Đáp án cho truy vấn thứ i 
  61.  
  62. void add(int i) {
  63. 	int u = euler_tour[i]; 
  64. 	cnt[c[u]]++;  
  65. 	suf[cnt[c[u]]]++; 
  66. }
  67.  
  68. void remove(int i) {
  69. 	int u = euler_tour[i]; 
  70. 	suf[cnt[c[u]]]--; 
  71. 	cnt[c[u]]--; 
  72. }
  73.  
  74. int main() {
  75. 	ios::sync_with_stdio(false); 
  76. 	cin.tie(nullptr); 	
  77. 	cin >> n >> q; 
  78. 	for (int u = 1; u <= n; u++) cin >> c[u]; 
  79.  
  80. 	for (int i = 0; i < n - 1; i++) {
  81. 		int u, v; 
  82. 		cin >> u >> v; 
  83. 		adj[u].push_back(v); 
  84. 		adj[v].push_back(u); 
  85. 	}
  86.  
  87. 	timer = 0;  
  88. 	dfs(1, -1);   
  89.  
  90. 	for (int i = 0; i < q; i++) {
  91. 		int v, k; 
  92. 		cin >> v >> k;  
  93. 		queries.push_back({tin[v], tout[v], k, i}); 
  94. 	}
  95.  
  96. 	sort(queries.begin(), queries.end());   
  97.  
  98. 	int cur_l = 1, cur_r = 0; 
  99. 	for (Query &q : queries) {
  100. 		while (cur_l > q.l) add(--cur_l); 
  101. 		while (cur_r < q.r) add(++cur_r); 
  102. 		while (cur_l < q.l) remove(cur_l++); 
  103. 		while (cur_r > q.r) remove(cur_r--); 
  104.  
  105. 		ans[q.idx] = suf[q.k]; 
  106. 	}
  107.  
  108. 	for (int i = 0; i < q; i++) cout << ans[i] << '\n'; 
  109. }
Success #stdin #stdout 0.01s 7048KB
comments (?)
stdin
copy 
8 5
1 2 2 3 3 2 3 3
1 2
1 5
2 3
2 4
5 6
5 7
5 8
1 2
1 3
1 4
2 3
5 3
stdout
copy 
2
2
1
0
1
https://ideone.com/LR1uTW
language:
C++14 (gcc 8.3)
created:
179 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!