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 = 4e5 + 5; 
  12.  
  13. int n, q;  
  14. int c[N]; 
  15. vector<int> adj[N]; 
  16.  
  17. int tin[N], tout[N], timer;  
  18.  
  19. void dfs(int u, int p) {
  20. 	tin[u] = ++timer; 
  21. 	for (int v : adj[u]) {
  22. 		if (v == p) continue; 
  23. 		dfs(v, u); 
  24. 	}
  25. 	tout[u] = timer; 
  26. }
  27.  
  28. struct SegTree {
  29. 	int n;   
  30. 	vector<ll> seg; 
  31. 	vector<ll> lazy;  
  32.  
  33. 	SegTree(int n) : n(n) {
  34. 		seg.resize(4 * n, 0);  
  35. 		lazy.resize(4 * n, -1); 
  36. 	}
  37.  
  38. 	void push(int id) {
  39. 		if (lazy[id] != -1) {
  40. 			seg[id * 2] = lazy[id * 2] = lazy[id]; 
  41. 			seg[id * 2 + 1] = lazy[id * 2 + 1] = lazy[id]; 
  42. 			lazy[id] = -1; 
  43. 		}
  44. 	}
  45.  
  46. 	void update(int id, int l, int r, int u, int v, ll val) {
  47. 		if (l > v || r < u) return; 
  48. 		if (u <= l && r <= v) {
  49. 			seg[id] = val;   
  50. 			lazy[id] = val;  
  51. 			return; 
  52. 		}
  53. 		push(id); 
  54. 		int mid = (l + r) >> 1; 
  55. 		update(id * 2, l, mid, u, v, val); 
  56. 		update(id * 2 + 1, mid + 1, r, u, v, val); 
  57. 		seg[id] = seg[id * 2] | seg[id * 2 + 1]; 
  58. 	}
  59.  
  60. 	ll get(int id, int l, int r, int u, int v) {
  61. 		if (l > v || r < u) return 0; 
  62. 		if (u <= l && r <= v) return seg[id]; 
  63. 		push(id); 
  64. 		int mid = (l + r) >> 1; 
  65. 		return (get(id * 2, l, mid, u, v) | get(id * 2 + 1, mid + 1, r, u, v)); 
  66. 	}
  67. }; 
  68.  
  69. // - Cây con gốc u sẽ tương ứng với đoạn [tin(u), tout(u)] trên Euler Tour
  70. // => Biến đổi lại truy vấn trong bài sẽ là update 1 đoạn và get 1 đoạn
  71. // - Do giới hạn của c(i) đủ nhỏ (1 <= c(i) <= 60) nên ta có thể dùng 60 cây segment tree để quản lí mỗi màu
  72. // => Độ phức tạp O(q * 60 * log2(n))
  73. // - Nhưng giới hạn bài này khá căng nên cần phải tối ưu thêm
  74. // - Cũng dựa vào giới hạn của c(i), ta có thể xem mỗi màu c ứng với một mask 2^c (chỉ có bit c bật và các bit còn lại đều tắt)
  75. //	 Khi đó giá trị mask tương ứng với 1 đoạn sẽ là tổng OR của đoạn đó (tức các màu c có xuất hiện trong đoạn thì các bit tương ứng sẽ được bật)
  76. //   Và giá trị mask lớn nhất sẽ là 2^61 - 1 (các bit từ 0 đến 60 đều được bật) => Đủ trong phạm vi kiểu long long
  77. // => Chỉ cần dùng 1 cây Segment Tree
  78. // => Độ phức tạp O(q * log2(n))
  79.  
  80. int main() {
  81. 	ios::sync_with_stdio(false); 
  82. 	cin.tie(nullptr); 	
  83. 	cin >> n >> q;  
  84. 	for (int u = 1; u <= n; u++) {
  85. 		cin >> c[u];
  86. 	}
  87.  
  88. 	for (int i = 0; i < n - 1; i++) {
  89. 		int u, v; 
  90. 		cin >> u >> v; 
  91. 		adj[u].push_back(v); 
  92. 		adj[v].push_back(u); 
  93. 	}
  94.  
  95. 	timer = 0; 
  96. 	dfs(1, -1); 
  97.  
  98. 	SegTree segtree(n + 1);  
  99. 	for (int u = 1; u <= n; u++) {
  100. 		segtree.update(1, 1, n, tin[u], tin[u], 1ll << c[u]); 
  101. 	}
  102.  
  103. 	while (q--) {
  104. 		int type, u; 
  105. 		cin >> type >> u;  
  106.  
  107. 		if (type == 1) {
  108. 			int val; 
  109. 			cin >> val;  
  110. 			segtree.update(1, 1, n, tin[u], tout[u], 1ll << val); 
  111. 		}	
  112. 		else {
  113. 			ll mask = segtree.get(1, 1, n, tin[u], tout[u]); 
  114. 			cout << __builtin_popcountll(mask) << '\n'; 
  115. 		}
  116. 	}
  117. }
Success #stdin #stdout 0.01s 14312KB
comments (?)
stdin
copy 
7 10
1 1 1 1 1 1 1
1 2
1 3
1 4
3 5
3 6
3 7
1 3 2
2 1
1 4 3
2 1
1 2 5
2 1
1 6 4
2 1
2 2
2 3
stdout
copy 
2
3
4
5
1
2
https://ideone.com/fnEb5H
language:
C++14 (gcc 8.3)
created:
180 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!