fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 10000 + 10;
  6. const int Q = 100000 + 10;
  7. const int LOG = 15;
  8.  
  9. struct Node {
  10. 	int val, lc, rc;
  11. };
  12.  
  13. int a[N];
  14. int ver[Q];
  15. Node mem[2*N+Q*LOG];
  16. int tot;
  17.  
  18. int build(int begin, int end) {
  19. 	if (begin == end) {
  20. 		mem[tot].val = a[begin];
  21. 		return tot ++;
  22. 	}
  23. 	int mid = (begin + end) / 2, u = tot ++;
  24. 	mem[u].lc = build(begin, mid);
  25. 	mem[u].rc = build(mid + 1, end);
  26. 	mem[u].val = max(mem[mem[u].lc].val, mem[mem[u].rc].val);
  27. 	return u;
  28. }
  29.  
  30. int update(int root, int begin, int end, int loc, int val) {
  31. 	if (begin == end) {
  32. 		mem[tot].val = val;
  33. 		return tot ++;
  34. 	}
  35. 	int mid = (begin + end) / 2, u = tot ++;
  36. 	if (loc <= mid) {
  37. 		mem[u].lc = update(mem[root].lc, begin, mid, loc, val);
  38. 		mem[u].rc = mem[root].rc;
  39. 	}
  40. 	else {
  41. 		mem[u].lc = mem[root].lc; 
  42. 		mem[u].rc = update(mem[root].rc, mid + 1, end, loc, val);
  43. 	}
  44. 	mem[u].val = max(mem[mem[u].lc].val, mem[mem[u].rc].val);
  45. 	return u;
  46. }
  47.  
  48. int query(int root, int begin, int end, int left, int right) {
  49. 	if (left <= begin && right >= end) return mem[root].val;
  50. 	int mid = (begin + end) / 2;
  51. 	if (right <= mid) return query(mem[root].lc, begin, mid, left, right);
  52. 	else if (left > mid) return query(mem[root].rc, mid + 1, end, left, right);
  53. 	else return max(query(mem[root].lc, begin, mid, left, mid), query(mem[root].rc, mid + 1, end, mid + 1, right));
  54. }
  55.  
  56. int main() {
  57. 	int n, q, s = 0, op, k, p, v, l, r;
  58. 	scanf("%d %d", &n, &q);
  59. 	for (int i=1; i<=n; i++) scanf("%d", &a[i]);
  60. 	ver[++s] = build(1, n);
  61. 	while (q --) {
  62. 		scanf("%d %d", &op, &k);
  63. 		if (op == 0) {
  64. 			scanf("%d %d", &l, &r);
  65. 			printf("%d\n", query(ver[k], 1, n, l, r));
  66. 		}
  67. 		else {
  68. 			scanf("%d %d", &p, &v);
  69. 			ver[++s] = update(ver[k], 1, n, p, v);
  70. 		}
  71. 	}
  72. 	return 0;
  73. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bDy7kz
language:
C++ (gcc 8.3)
created:
292 days 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!