fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int size=1<<16;
  5. int a[size];
  6.  
  7. struct node{
  8. 	int sum;
  9.  
  10. 	node split(node& l, node& r){};
  11.  
  12. 	node merge(node& l, node& r){
  13. 		sum = l.sum + r.sum;
  14. 	}
  15.  
  16. 	node setVal(int val){
  17. 		sum = val;
  18. 	}
  19. };
  20.  
  21. node T[size<<1],lazy[size<<1];
  22.  
  23. void init(int Node, int i, int j){
  24. 	if(i==j){
  25. 		T[Node].setVal(a[i]);//for leaf nodes
  26. 		return;
  27. 	}
  28.  
  29. 	int mid = (i+j)>>1;
  30.  
  31. 	init(Node*2,i,mid);
  32. 	init(Node*2+1,mid+1,j);
  33.  
  34. 	T[Node].merge(T[Node*2],T[Node*2+1]);
  35. }
  36.  
  37. void update(int Node, int i, int j, int x,int y, int val){
  38.  
  39. 	if(lazy[Node].sum!=0){
  40. 		// This node needs to be updated
  41.  
  42. 		T[Node].setVal(T[Node].sum + lazy[Node].sum);				// update it
  43.  
  44. 		if(i!=j){
  45. 			lazy[2*Node].setVal(lazy[2*Node].sum + lazy[Node].sum); 	// Mark child as lazy
  46. 			lazy[2*Node+1].setVal(lazy[2*Node+1].sum + lazy[Node].sum); // Mark child as lazy
  47. 		}
  48.  
  49. 		lazy[Node].sum=0;									// reset
  50. 	}
  51.  
  52. 	if(i>y||j<x || i>j)	return;					/// doesnot lie within the range
  53.  
  54. 	if(i>=x&&j<=y){								// lie within the range x,y
  55.  
  56. 		T[Node].setVal(T[Node].sum + val);
  57.  
  58. 		if(i!=j){
  59. 			lazy[2*Node].setVal(lazy[2*Node].sum + val);
  60. 			lazy[2*Node+1].setVal(lazy[2*Node+1].sum + val);
  61. 		}
  62.  
  63. 		return;
  64. 	}
  65.  
  66.  
  67.  
  68. 	int mid=(i+j)>>1;
  69.  
  70. 	update(2*Node,i,mid,x,y,val);
  71. 	update(2*Node+1,mid+1,j,x,y,val);
  72.  
  73. 	T[Node].merge(T[2*Node],T[2*Node+1]);
  74. }
  75.  
  76. void range_query(node& resultNode, int Node, int i, int j, int x, int y){
  77.  
  78. 	if(i>j || i>y || j<x) {resultNode.sum=0;return;}
  79.  
  80. 	if(lazy[Node].sum!=0){
  81. 		// This node needs to be updated
  82.  
  83. 		T[Node].setVal(T[Node].sum + lazy[Node].sum);				// update it
  84.  
  85. 		if(i!=j){
  86. 			lazy[2*Node].setVal(lazy[2*Node].sum + lazy[Node].sum); 	// Mark child as lazy
  87. 			lazy[2*Node+1].setVal(lazy[2*Node+1].sum + lazy[Node].sum); // Mark child as lazy
  88. 		}
  89.  
  90. 		lazy[Node].sum=0;									// reset
  91. 	}
  92.  
  93.  
  94. 	if(i>=x&&j<=y){
  95. 		resultNode=T[Node];
  96. 		return;
  97. 	}
  98.  
  99. 	int mid=(i+j)>>1;
  100.  
  101. 	if(y<=mid){//if range completely lies in the left part
  102. 		range_query(resultNode,Node*2,i,mid,x,y);
  103. 	}
  104. 	else if(x>mid){//if range completely lies in the right part
  105. 		range_query(resultNode,Node*2+1,mid+1,j,x,y);
  106. 	}
  107. 	else{//lies partly in the range
  108. 		node left, right;
  109. 		range_query(left,Node*2,i,mid,x,y);
  110. 		//keep the rightmost boundary fixed and find the left index
  111. 		// as it lies partly in both range so mid will be same 
  112. 		// only we have to find the left part
  113. 		range_query(right,Node*2+1,mid+1,j,x,y);
  114. 		// same condition for right node mid+1 will be fixed
  115.  
  116. 		resultNode.merge(left,right);
  117. 	}
  118. }
  119.  
  120.  
  121.  
  122. int main() {
  123. 	int i,n,m,x,y,t;
  124. 	node res;
  125. 	scanf("%d",&t);
  126.  
  127. 	while(t--){
  128. 		scanf("%d %d",&n,&m);
  129.  
  130. 		for(i=0;i<n;i++){
  131. 			a[i]=0;
  132. 		}
  133.  
  134. 		init(1,0,n-1);
  135.  
  136. 		while(m--){
  137.  
  138. 			int op,x,y,val;
  139. 			scanf("%d",&op);
  140.  
  141. 			if(op==1){
  142. 				scanf("%d %d",&x,&y);
  143. 				range_query(res,1,0,n-1,x-1,y-1);
  144. 				printf("%d\n",res.sum);
  145. 			}else{
  146. 				scanf("%d %d %d",&x,&y,&val);
  147. 				update(1, 0, n-1, x-1, y-1, val);
  148. 			}
  149. 		}
  150. 	}	
  151.  
  152. 	return 0;
  153. }
Success #stdin #stdout 0s 4752KB
comments (?)
stdin
copy 
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8 
0 5 7 14
1 4 8
stdout
copy 
80
494
https://ideone.com/XwHMrW
problem GSS1, based on SPOJ submission 17732140 (C++14), 2016-09-17 20:44:01
language:
C++14 (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!