fork download
copy 
  1. #include <cmath>
  2. #include <vector>
  3. #include <cassert>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7. #pragma warning(disable : 4996)
  8. const int inf = 1512345678;
  9. int N, Q, c, cr, p[500009], tp[500009], v[500009], d[500009], ql[500009], qr[500009], qd[500009], x[500009]; long long a[500009], at[500009];
  10. vector<int> g[500009]; int depth[500009], ord[500009], gl[500009], gr[500009], rd[500009];
  11. void rec(int pos) {
  12. 	int pd = depth[cr];
  13. 	gl[pos] = cr;
  14. 	ord[cr++] = pos;
  15. 	for (int i : g[pos]) rd[cr] = depth[cr] = pd + 1, rec(i);
  16. 	gr[pos] = cr;
  17. }
  18. int main() {
  19. 	cin >> N >> Q;
  20. 	for (int i = 0; i < N; i++) scanf("%d %lld", &p[i], &at[i]);
  21. 	c = N;
  22. 	for (int i = 0; i < Q; i++) {
  23. 		cin >> tp[i];
  24. 		if (tp[i] == 1) scanf("%d %d %d", &v[i], &d[i], &x[i]);
  25. 		if (tp[i] == 2) scanf("%d %d", &v[i], &d[i]);
  26. 		if (tp[i] == 3) scanf("%d %lld", &p[c], &at[c]), c++;
  27. 	}
  28. 	for (int i = 1; i < c; i++) g[p[i]].push_back(i);
  29. 	rec(0);
  30. 	for (int i = 0; i < c; i++) a[i] = at[ord[i]];
  31. 	int pl = 0, pr = N;
  32. 	for (int i = 0; i < Q; i++) {
  33. 		if (tp[i] != 3) ql[i] = gl[v[i]], qr[i] = gr[v[i]], qd[i] = depth[gl[v[i]]] + d[i] + 1;
  34. 		else ql[i] = gl[pr], qr[i] = gl[pr] + 1, pr++;
  35. 	}
  36. 	for (int i = 0; i < c; i++) {
  37. 		if (ord[i] >= N) depth[i] = inf;
  38. 	}
  39. 	// Query 1: l = ql[i], r = qr[i], d = qd[i], x = qx[i] (l <= i < r, y < d)
  40. 	// Query 2: l = ql[i], r = qr[i], d = qd[i]
  41. 	// Query 3: v = ql[i]
  42. 	int B = sqrt(Q)/7+1;
  43. 	for (int i = 0; i < B; i++) {
  44. 		int bl = i * Q / B, br = (i + 1) * Q / B;
  45. 		vector<int> v;
  46. 		for (int j = bl; j < br; j++) {
  47. 			v.push_back(ql[j]);
  48. 			v.push_back(qr[j]);
  49. 		}
  50. 		v.push_back(0);
  51. 		v.push_back(c);
  52. 		sort(v.begin(), v.end());
  53. 		v.erase(unique(v.begin(), v.end()), v.end());
  54. 		vector<vector<int> > vd(v.size() - 1), vperm(v.size() - 1);
  55. 		vector<vector<long long> > bit1(v.size() - 1), bit0(v.size() - 1), gsum(v.size() - 1);
  56. 		for (int j = 0; j < v.size() - 1; j++) {
  57. 			vd[j].resize(v[j + 1] - v[j]);
  58. 			vperm[j].resize(v[j + 1] - v[j]);
  59. 			gsum[j].resize(v[j + 1] - v[j] + 1);
  60. 			bit1[j].resize(v[j + 1] - v[j] + 1);
  61. 			bit0[j].resize(v[j + 1] - v[j] + 1);
  62. 			for (int k = v[j]; k < v[j + 1]; k++) vd[j][k - v[j]] = depth[k], vperm[j][k - v[j]] = k;
  63. 			sort(vperm[j].begin(), vperm[j].end(),
  64. 				[&](int k, int l) -> bool { return depth[k] < depth[l]; }
  65. 			);
  66. 			for (int k = v[j]; k < v[j + 1]; k++) vd[j][k - v[j]] = depth[vperm[j][k - v[j]]], gsum[j][k - v[j] + 1] = a[vperm[j][k - v[j]]];
  67. 			for (int k = 0; k < v[j + 1] - v[j]; k++) gsum[j][k + 1] += gsum[j][k];
  68. 		}
  69. 		for (int j = bl; j < br; j++) {
  70. 			if (tp[j] == 1) {
  71. 				int vl = lower_bound(v.begin(), v.end(), ql[j]) - v.begin();
  72. 				int vr = lower_bound(v.begin(), v.end(), qr[j]) - v.begin();
  73. 				for (int k = vl; k < vr; k++) {
  74. 					int ptr = lower_bound(vd[k].begin(), vd[k].end(), qd[j]) - vd[k].begin();
  75. 					for (int l = ptr + 1; l <= v[k + 1] - v[k]; l += l & (-l)) {
  76. 						bit1[k][l] -= x[j];
  77. 						bit0[k][l] += 1LL * x[j] * ptr;
  78. 					}
  79. 					for (int l = 1; l <= v[k + 1] - v[k]; l += l & (-l)) {
  80. 						bit1[k][l] += x[j];
  81. 					}
  82. 				}
  83. 			}
  84. 			if (tp[j] == 2) {
  85. 				int vl = lower_bound(v.begin(), v.end(), ql[j]) - v.begin();
  86. 				int vr = lower_bound(v.begin(), v.end(), qr[j]) - v.begin();
  87. 				long long ret = 0;
  88. 				for (int k = vl; k < vr; k++) {
  89. 					int ptr = lower_bound(vd[k].begin(), vd[k].end(), qd[j]) - vd[k].begin();
  90. 					for (int l = ptr; l >= 1; l -= l & (-l)) ret += bit1[k][l] * ptr + bit0[k][l];
  91. 					ret += gsum[k][ptr];
  92. 				}
  93. 				printf("%lld\n", ret);
  94. 			}
  95. 			if (tp[j] == 3) {
  96. 				int ptr = lower_bound(v.begin(), v.end(), ql[j] + 1) - v.begin() - 1;
  97. 				depth[ql[j]] = rd[ql[j]];
  98. 				vd[ptr][0] = rd[ql[j]];
  99. 			}
  100. 		}
  101. 		for (int j = 0; j < v.size() - 1; j++) {
  102. 			long long b_all = 0;
  103. 			for (int k = v[j + 1] - v[j]; k >= 1; k -= k & (-k)) b_all += bit1[j][k] * (v[j + 1] - v[j]) + bit0[j][k];
  104. 			vector<long long> b(v[j + 1] - v[j]);
  105. 			for (int k = 0; k < v[j + 1] - v[j]; k++) {
  106. 				b[k] += b_all;
  107. 				for (int l = k + 1; l >= 1; l -= l & (-l)) b[k] -= bit1[j][l] * k + bit0[j][l];
  108. 			}
  109. 			for (int k = 0; k < v[j + 1] - v[j] - 1; k++) b[k] -= b[k + 1];
  110. 			for (int k = v[j]; k < v[j + 1]; k++) {
  111. 				a[vperm[j][k - v[j]]] = b[k - v[j]] + gsum[j][k - v[j] + 1] - gsum[j][k - v[j]];
  112. 			}
  113. 		}
  114. 	}
  115. 	return 0;
  116. }
Success #stdin #stdout 0s 60992KB
comments (?)
stdin
copy 
6 7
-1 6
0 5
0 4
2 3
2 2
1 1
2 0 1
1 0 2 1
2 2 1
3 3 3
2 0 3
3 3 4
2 1 1
stdout
copy 
15
12
30
8
https://ideone.com/rc0sc7
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

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!