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. const int N = 2e5 + 5; 
  12.  
  13. int n, q;  
  14. int a[N]; 
  15.  
  16. vector<int> root;  
  17.  
  18. struct PersistentSegTree {
  19. 	struct Node {
  20. 		int l = 0, r = 0;  
  21. 		ll sum = 0;  
  22. 	};
  23.  
  24. 	int n;  
  25. 	vector<Node> seg;  
  26.  
  27. 	PersistentSegTree(int n) : n(n) {
  28. 		seg.reserve(22 * n);
  29. 	}
  30.  
  31. 	int build(int l, int r, int a[]) {
  32. 		int cur = seg.size();  
  33. 		seg.push_back(Node()); 
  34. 		if (l == r) {
  35. 			seg[cur].sum = a[l]; 
  36. 			return cur; 
  37. 		}
  38. 		int mid = (l + r) >> 1; 
  39. 		seg[cur].l = build(l, mid, a); 
  40. 		seg[cur].r = build(mid + 1, r, a); 
  41. 		int lc = seg[cur].l, rc = seg[cur].r;   
  42. 		seg[cur].sum = seg[lc].sum + seg[rc].sum;
  43. 		return cur; 
  44. 	}
  45.  
  46. 	int update(int pre, int l, int r, int pos, int val) {
  47. 		int cur = seg.size();  
  48. 		seg.push_back(seg[pre]); 
  49. 		if (l == r) {
  50. 			seg[cur].sum = val;  
  51. 			return cur; 
  52. 		}
  53. 		int mid = (l + r) >> 1;  
  54. 		if (pos <= mid) {
  55. 			seg[cur].l = update(seg[pre].l, l, mid, pos, val);  
  56. 		}
  57. 		else {
  58. 			seg[cur].r = update(seg[pre].r, mid + 1, r, pos, val); 
  59. 		}
  60. 		int lc = seg[cur].l, rc = seg[cur].r;  
  61. 		seg[cur].sum = seg[lc].sum + seg[rc].sum; 
  62. 		return cur; 
  63. 	}
  64.  
  65. 	ll getSum(int rt, int l, int r, int u, int v) {
  66. 		if (l > v || r < u) return 0;  
  67. 		if (u <= l && r <= v) return seg[rt].sum;  
  68. 		int mid = (l + r) >> 1; 
  69. 		return getSum(seg[rt].l, l, mid, u, v) + getSum(seg[rt].r, mid + 1, r, u, v);
  70. 	}
  71.  
  72. 	int build(int a[]) {
  73. 		return build(1, n, a);
  74. 	}
  75.  
  76. 	int update(int pre, int pos, int val) {
  77. 		return update(pre, 1, n, pos, val);
  78. 	}
  79.  
  80. 	ll getSum(int rt, int u, int v) {
  81. 		return getSum(rt, 1, n, u, v); 
  82. 	}
  83. }; 
  84.  
  85. int main() {
  86. 	ios::sync_with_stdio(false); 
  87. 	cin.tie(nullptr); 	
  88. 	cin >> n >> q; 
  89. 	for (int i = 1; i <= n; i++) cin >> a[i];  
  90.  
  91. 	PersistentSegTree pst(n);  
  92. 	root.push_back(pst.build(a));  
  93.  
  94. 	while (q--) {
  95. 		int type, k; 
  96. 		cin >> type >> k;  
  97. 		--k;   
  98. 		if (type == 1) {
  99. 			int pos, val; 
  100. 			cin >> pos >> val;  
  101. 			root[k] = pst.update(root[k], pos, val); 
  102. 		}
  103. 		else if (type == 2) {
  104. 			int l, r; 
  105. 			cin >> l >> r; 
  106. 			cout << pst.getSum(root[k], l, r) << '\n'; 
  107. 		}
  108. 		else {
  109. 			root.push_back(root[k]);
  110. 		}
  111. 	}
  112. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
5 6
2 3 1 2 5
3 1
2 1 1 5
2 2 1 5
1 2 2 5
2 1 1 5
2 2 1 5
stdout 
13
13
13
15
https://ideone.com/EgLUdD
language:
C++14 (gcc 8.3)
created:
13 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!