fork download
copy 
  1. #include <iostream>
  2. #include <string.h>
  3. #include <vector>
  4. #include <set>
  5. using namespace std;
  6.  
  7. struct E{
  8. 	long long int num,no;
  9. 	bool commit;
  10. };
  11. struct E2{
  12. 	int l,r,x,y,z;
  13. };
  14. const int maxS=600000;
  15. int R=262143;
  16. int no0=0;
  17. vector<E2> copyData;
  18. vector<long long int> areaSum;
  19. E segA[maxS];
  20.  
  21. long long int fSegASet(int no,int p1,int l2,int r2,long long int num){
  22. 	if(r2<p1 || p1<l2)return segA[no].num;
  23. 	if(l2==r2){
  24. 		segA[no].num=num;
  25. 		return segA[no].num;
  26. 	}
  27. 	int m=(l2+r2)/2;
  28. 	long long int res=fSegASet(no*2+1,p1,l2,m,num);
  29. 	res+=fSegASet(no*2+2,p1,m+1,r2,num);
  30. 	segA[no].num=res;
  31. 	return res;
  32. }
  33.  
  34. long long int calc(int no,int no2,int no3,int l,int r,int l2,int r2,bool commit){
  35. 	//cout<<"<"<<commit<<" "<<no<<",no2="<<no2<<",no3="<<no3<<",l="<<l<<",r="<<r<<","<<l2<<","<<r2<<",>";
  36.  
  37. 	if(commit==true){
  38. 		//cout<<1<<" "<<segA[no].num<<endl;
  39. 		if(l2==4 && r2==5){
  40. 			cout<<"?1>"<<segA[no].num<<endl;
  41. 		}
  42. 		return segA[no].num;
  43. 	}else{
  44. 		E2 e2=copyData[no2];
  45. 		if(e2.x<=l2 && r2<=e2.x+e2.z){
  46. 			int l3=e2.y+(l2-e2.x+1);
  47. 			int r3=l3+(r2-l2)+1;
  48. 			long long int t=areaSum[r3]-areaSum[l3];
  49. 			if(l2==4 && r2==5){
  50. 				cout<<"?2>"<<t<<endl;
  51. 			}
  52. 			return t;
  53. 		}
  54. 		e2=copyData[no3];
  55. 		//cout<<3<<e2.x<<" "<<e2.z<<endl;
  56.  
  57. 		long long int t=areaSum[e2.x+e2.z]-areaSum[e2.x];
  58. 		if(l2==4 && r2==5){
  59. 			cout<<"?3>"<<t<<endl;
  60. 		}
  61. 		return t;
  62. 	}
  63. }
  64.  
  65.  
  66. long long int fSegACalcAns(int no,int l,int r,int l2,int r2,int no2,bool commit){
  67. 	commit=commit && segA[no].commit;
  68. 	no2=(no2<segA[no].no)?segA[no].no:no2;
  69. 	long long int res=calc(no,no2,no2,l,r,l2,r2,commit);
  70. 	if(r2<l || r<l2)return 0;
  71.  
  72. 	if(l2==r2){
  73.  
  74. 		return res;
  75. 	}
  76. 	if(l<=l2 && r2<=r){
  77. 		return res;
  78. 	}else{
  79. 		int m=(l2+r2)/2;
  80. 		res=fSegACalcAns(no*2+1,l,r,l2,m,no2,commit);
  81. 		res+=fSegACalcAns(no*2+2,l,r,m+1,r2,no2,commit);
  82. 		return res;
  83. 	}
  84. }
  85.  
  86. long long int fSegAUpData(int no,int l,int r,int l2,int r2,int no2,int no3,bool commit){
  87. 	commit=commit && segA[no].commit;
  88. 	no3=(no3<segA[no].no)?segA[no].no:no3;
  89. 	long long int res=calc(no,no2,no3,l,r,l2,r2,commit);
  90. 	if(r2<l || r<l2)return res;
  91. 	res=calc(no,no2,no3,l,r,l2,r2,false);
  92. 	segA[no].commit=true;
  93.  
  94. 	if(l2==r2){
  95.  
  96. 		segA[no].no=no0;
  97. 		segA[no].num=res;
  98. 		segA[no].commit=true;
  99. 		return res;
  100. 	}
  101. 	if(l<=l2 && r2<=r){
  102. 		segA[no].no=no0;
  103. 		segA[no].num=res;
  104. 		segA[no].commit=true;
  105. 		segA[no*2+1].commit=false;
  106. 		segA[no*2+2].commit=false;
  107. 		return res;
  108. 	}else{
  109. 		int m=(l2+r2)/2;
  110. 		res=fSegAUpData(no*2+1,l,r,l2,m,no2,no3,commit);
  111. 		res+=fSegAUpData(no*2+2,l,r,m+1,r2,no2,no3,commit);
  112. 		segA[no].num=res;
  113. 		segA[no].commit=true;
  114. 		return res;
  115. 	}
  116. }
  117.  
  118. int main() {
  119. 	for(int i=0;i<maxS;i++){
  120. 		segA[i].num=0;
  121. 		segA[i].no=-1;
  122. 		segA[i].commit=true;
  123. 	}
  124. 	int n,m;
  125. 	cin>>n>>m;
  126. 	for(int i=0;i<n;i++){
  127. 		long long int num;
  128. 		cin>>num;
  129. 		fSegASet(0,i,0,R,num);
  130. 	}
  131. 	areaSum.push_back(0);
  132. 	long long int sum=0;
  133. 	for(int i=0;i<n;i++){
  134. 		long long int num;
  135. 		cin>>num;
  136. 		sum+=num;
  137. 		areaSum.push_back(sum);
  138. 	}
  139. 	for(int i=0;i<maxS;i++){
  140. 		areaSum.push_back(sum);
  141. 	}
  142.  
  143. 	for(int i=0;i<m;i++){
  144. 		int c1,l,r,x,y,z;
  145. 		cin>>c1;
  146. 		if(c1==0){
  147. 			cin>>x>>y>>z;
  148. 			E2 e2;
  149. 			e2.l=y-1;
  150. 			e2.r=y-2+z;
  151. 			e2.x=x-1;
  152. 			e2.y=y-1;
  153. 			e2.z=z;
  154. 			l=x-1;
  155. 			r=x-2+z;
  156. 			copyData.push_back(e2);
  157. 			fSegAUpData(0,l,r,0,R,no0,-1,true);
  158. 			no0++;
  159. 		}else{
  160. 			cin>>l>>r;
  161. 			l--;
  162. 			r--;
  163. 			long long int t=fSegACalcAns(0,l,r,0,R,-1,true);
  164. 			cout<<t<<endl;
  165. 		}
  166. 		//for(int i=0;i<maxS;i++){
  167. 			//cout<<"("<<i<<","<<segA[i].num<<")";
  168. 		//}
  169. 	//cout<<endl;
  170. 	}
  171. 	return 0;
  172. }
Success #stdin #stdout 0.02s 26088KB
comments (?)
stdin
copy 
10 36
9 9 11 4 3 6 11 11 8 2
7 3 2 1 3 8 9 5 11 6
0 7 5 2
1 3 7
1 4 9
0 3 7 1
0 5 6 2
1 7 7
0 9 3 1
1 7 9
0 1 1 3
1 4 8
0 4 1 3
1 3 6
1 0 3
1 10 10
1 5 10
1 1 1
0 5 10 1
0 1 4 4
1 5 6
1 1 1
1 2 2
1 3 3
1 4 4
1 5 5
1 6 6
1 7 7
1 8 8
1 9 9
1 10 10
0 1 1 10
1 1 10
1 1 6
0 1 4 3
1 1 6
0 3 1 3
1 1 6
stdout
copy 
?1>9
?1>9
32
38
?1>9
?2>14
?1>14
8
?1>14
18
35
?1>14
?2>3
?1>3
7
6
2
23
3
?1>3
?2>0
?1>0
0
3
8
9
5
?1>0
0
?1>0
1
?1>0
8
?1>0
9
1
2
48
?2>17
26
?2>17
42
?2>4
?2>4
?1>4
20
https://ideone.com/aJjctA
language:
C++ (gcc 8.3)
created:
7 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!