fork download 
  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. // - Dữ kiện quan trọng: x(u) = -1 hoặc 1
  12. // - Nhận xét:
  13. //   Xét một đoạn con bất kì trên đường đi từ u đến v có tổng là sum, 
  14. //   với mỗi thao tác bổ sung một đỉnh vào đoạn hoặc xoá một đỉnh khỏi đoạn, giá trị của sum tăng/giảm 1 đơn vị
  15. // => Giá trị của sum là liên tục
  16. // => Nếu ta biết được giá trị của đoạn con có tổng lớn nhất (mx_sub) và đoạn con có tổng nhỏ nhất (mn_sub), thì một giá trị k bất kì 
  17. //    thoả mãn tồn tại một đoạn con trên đường đi từ u đến v có tổng bằng k nếu k thuộc đoạn [mn_sub, mx_sub] 
  18. // => Với mỗi truy vấn, thay vì tìm đoạn con có tổng = k (một bài toán khó giải quyết hơn),
  19. //    ta đi tìm đoạn con có tổng lớn nhất và đoạn con có tổng nhỏ nhất trên đường đi từ u đến v rồi kiểm tra k có thuộc đoạn này không
  20. // - Lưu ý hàm combine() trong bài này không có tính chất giao hoán nên cần xử lí theo đúng chiều đường đi từ u đến v
  21.  
  22. const int N = 2e5 + 5; 
  23. const int LOG = 18;  
  24.  
  25. int n, q; 
  26. int x[N]; 
  27.  
  28. struct Data {
  29. 	int mx_sub, mx_pref, mx_suf; // max subarray sum/max prefix sum/max suffix sum
  30. 	int mn_sub, mn_pref, mn_suf; // min subarray sum/min prefix sum/min suffix sum
  31. 	int sum; // total sum
  32.  
  33. 	Data(int x = 0) {
  34. 		mx_sub = mx_pref = mx_suf = max(0, x);   
  35. 		mn_sub = mn_pref = mn_suf = min(0, x); 
  36. 		sum = x;  
  37. 	}
  38. };
  39.  
  40. Data combine(const Data& a, const Data& b) {
  41. 	Data ans;  
  42. 	ans.mx_sub = max({a.mx_sub, b.mx_sub, a.mx_suf + b.mx_pref}); 
  43. 	ans.mx_pref = max(a.mx_pref, a.sum + b.mx_pref);  
  44. 	ans.mx_suf = max(b.mx_suf, b.sum + a.mx_suf); 
  45. 	ans.mn_sub = min({a.mn_sub, b.mn_sub, a.mn_suf + b.mn_pref});  
  46. 	ans.mn_pref = min(a.mn_pref, a.sum + b.mn_pref);
  47. 	ans.mn_suf = min(b.mn_suf, b.sum + a.mn_suf); 
  48. 	ans.sum = a.sum + b.sum;
  49. 	return ans; 
  50. }
  51.  
  52. int up[LOG][N];
  53. Data f[LOG][N];  
  54. int depth[N]; 
  55.  
  56. int lca(int u, int v) {
  57. 	if (depth[u] < depth[v]) swap(u, v);
  58. 	int diff = depth[u] - depth[v]; 
  59. 	for (int i = 0; i < LOG; i++) {
  60. 		if ((diff >> i) & 1) {
  61. 			u = up[i][u]; 
  62. 		}
  63. 	} 
  64. 	if (u == v) return u; 
  65. 	for (int i = LOG - 1; i >= 0; i--) {
  66. 		if (up[i][u] != up[i][v]) {
  67. 			u = up[i][u]; 
  68. 			v = up[i][v];
  69. 		}
  70. 	}
  71. 	return up[0][u]; 
  72. }
  73.  
  74. Data query(int u, int anc) {
  75. 	int diff = depth[u] - depth[anc]; 
  76. 	Data ans;  
  77. 	for (int i = 0; i < LOG; i++) {
  78. 		if ((diff >> i) & 1) {
  79. 			ans = combine(ans, f[i][u]); 
  80. 			u = up[i][u]; 
  81. 		}
  82. 	}
  83. 	return ans; 
  84. }
  85.  
  86. void solve() {
  87. 	cin >> q; 
  88. 	n = 1;  
  89. 	x[1] = 1; 
  90. 	depth[1] = 0;  
  91. 	up[0][1] = 1; 
  92. 	f[0][1] = Data(x[1]); 
  93. 	for (int i = 0; i < q; i++) {
  94. 		char type; cin >> type; 
  95. 		if (type == '+') {
  96. 			int u, v = ++n;   
  97. 			cin >> u >> x[v]; 
  98. 			depth[v] = depth[u] + 1;  
  99. 			up[0][v] = u;  
  100. 			f[0][v] = Data(x[v]); 
  101. 			for (int i = 1; i < LOG; i++) {
  102. 				up[i][v] = up[i - 1][up[i - 1][v]]; 
  103. 				f[i][v] = combine(f[i - 1][v], f[i - 1][up[i - 1][v]]); 
  104. 			}
  105. 		}
  106. 		else {
  107. 			int u, v, k; 
  108. 			cin >> u >> v >> k; 
  109. 			// u -> lca_uv -> v
  110. 			int lca_uv = lca(u, v);   
  111. 			Data ans = combine(query(u, lca_uv), Data(x[lca_uv]));  
  112. 			Data other = query(v, lca_uv);  
  113. 			swap(other.mx_pref, other.mx_suf); 
  114. 			swap(other.mn_pref, other.mn_suf); 
  115. 			ans = combine(ans, other); 
  116. 			cout << ((ans.mn_sub <= k && k <= ans.mx_sub) ? "YES" : "NO") << '\n'; 
  117. 		}
  118. 	}
  119. }
  120.  
  121. int main() {
  122. 	ios::sync_with_stdio(false); 
  123. 	cin.tie(nullptr); 	
  124. 	int t; cin >> t; 
  125. 	while (t--) {
  126. 		solve(); 
  127. 	}
  128. }
  129.  
Success #stdin #stdout 0.03s 116236KB
comments (?)
stdin 
1
8
+ 1 -1
? 1 1 2
? 1 2 1
+ 1 1
? 1 3 -1
? 1 1 1
? 1 3 2
? 1 1 0
stdout 
NO
YES
NO
YES
YES
YES
https://ideone.com/639WuS
language:
C++14 (gcc 8.3)
created:
173 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!