fork(2) download
copy 
  1. /**
  2. 	Template by Akikaze (秋風) - formerly proptit_4t41.
  3. 	Code written by a random fan of momocashew and Chiho.
  4. **/
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. /** -----BASIC MACROES----- **/
  10. #define endl '\n'
  11. #define i64 long long
  12. #define ld long double
  13. #define pub push_back
  14. #define mp make_pair
  15. #define fi first
  16. #define se second
  17. const long long MOD = 1000000007LL, INF = 1e9, LINF = 1e18;
  18. const long double PI = 3.141592653589793116, EPS = 1e-9, GOLD = ((1+sqrt(5))/2);
  19. typedef vector<i64> vi;
  20. typedef vector<ld> vd;
  21. typedef vector<string> vs;
  22. typedef vector<bool> vb;
  23. typedef pair<i64, i64> pii;
  24. typedef pair<i64, pii> pip;
  25. typedef pair<pii, i64> ppi;
  26.  
  27. /** -----BIT CONTROLS----- **/
  28. template<class T> int getbit(T s, int i) { return (s >> 1) & 1; }
  29. template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
  30. template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
  31. template<class T> int cntbit(T s) { return __builtin_popcount(s); }
  32.  
  33. /** -----IDEAS/ALGORITHMS-----
  34.  
  35.     -------------------------- **/
  36.  
  37. /** -----CUSTOM TYPEDEFS/DEFINES----- **/
  38. struct Node {
  39. 	i64 val = 0;
  40. 	i64 lazy = 0;
  41. };
  42.  
  43. /** -----GLOBAL VARIABLES----- **/
  44. i64 n, m;
  45. vector<Node> tree(666666);
  46.  
  47. /** -----EXTENSIVE FUNCTIONS----- **/
  48. void update(i64 node, i64 st, i64 en, i64 L, i64 R, i64 x) {
  49. 	if (tree[node].lazy > 0) {
  50. 		tree[node].val += tree[node].lazy;
  51. 		if (st != en) {
  52. 			tree[node*2].lazy += tree[node].lazy;
  53. 			tree[node*2+1].lazy += tree[node].lazy;
  54. 		}
  55. 		tree[node].lazy = 0;
  56. 	}
  57. 	if (st > en || st > R || en < L) return;
  58. 	if (L <= st && en <= R) {
  59. 		tree[node].val += x;
  60. 		if (st != en) {
  61. 			tree[node*2].lazy += x;
  62. 			tree[node*2+1].lazy += x;
  63. 		}
  64. 		return;
  65. 	}
  66. 	update(node*2, st, (st+en)/2, L, R, x);
  67. 	update(node*2+1, (st+en)/2+1, en, L, R, x);
  68. 	tree[node].val = max(tree[node*2].val, tree[node*2+1].val);
  69. }
  70.  
  71. i64 get(i64 node, i64 st, i64 en, i64 L, i64 R) {
  72. 	if (st > en || st > R || en < L) return -LINF;
  73. 	if (tree[node].lazy > 0) {
  74. 		tree[node].val += tree[node].lazy;
  75. 		if (st != en) {
  76. 			tree[node*2].lazy += tree[node].lazy;
  77. 			tree[node*2+1].lazy += tree[node].lazy;
  78. 		}
  79. 		tree[node].lazy = 0;
  80. 	}
  81. 	if (L <= st && en <= R) return tree[node].val;
  82. 	i64 p1 = get(node*2, st, (st+en)/2, L, R);
  83. 	i64 p2 = get(node*2+1, (st+en)/2+1, en, L, R);
  84. 	return max(p1, p2);
  85. }
  86.  
  87. /** -----COMPULSORY FUNCTIONS----- **/
  88. void VarInput() {
  89. 	cin >> n >> m;
  90. }
  91.  
  92. void ProSolve() {
  93. 	while (m--) {
  94. 		i64 cmd, l, r; cin >> cmd >> l >> r;
  95. 		if (cmd == 0) {
  96. 			i64 value; cin >> value;
  97. 			update(1, 1, n, l, r, value);
  98. 		}
  99. 		else cout << get(1, 1, n, l, r) << endl;
  100. 	}
  101. }
  102.  
  103. /** -----MAIN FUNCTION----- **/
  104. int main() {
  105. 	//freopen("FILE.INP", "r", stdin);
  106. 	//freopen("FILE.OUT", "w", stdout);
  107. 	ios_base::sync_with_stdio(0); cin.tie(NULL);
  108. 	VarInput(); ProSolve(); return 0;
  109. }
Success #stdin #stdout 0.01s 13292KB
comments (?)
stdin
copy 
6 3
0 1 3 3
0 4 6 4
1 1 6
stdout
copy 
4
https://ideone.com/Vr6Njc
Segment Tree - Lazy Propagation
language:
C++ (gcc 8.3)
created:
8 years 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!