fork(1) 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=16;//600000;
  15. int R=7;//262143
  16. int no2=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. 	if(commit==true){
  37. 		cout<<endl;
  38. 		return segA[no].num;
  39. 	}
  40. 	E2 e2=copyData[no3];
  41.  
  42. 	int l3=e2.y+(l2-e2.x);
  43. 	int r3=l3+(r2-l2)+1;
  44. 	return areaSum[r3]-areaSum[l3];
  45. }
  46.  
  47.  
  48. long long int fSegACalcAns(int no,int l,int r,int l2,int r2,int no2,bool commit){
  49. 	commit=commit && segA[no].commit;
  50. 	no2=(no2<segA[no].no)?segA[no].no:no2;
  51. 	long long int res=calc(no,no2,no2,l,r,l2,r2,commit);
  52. 	if(r2<l || r<l2)return 0;
  53. 	if(l2==r2){
  54. 		segA[no].no=no2;
  55. 		return res;
  56. 	}
  57. 	if(l<=l2 && r2<=r){
  58. 		segA[no].no=no2;
  59. 		return res;
  60. 	}else{
  61. 		int m=(l2+r2)/2;
  62. 		res=fSegACalcAns(no*2+1,l,r,l2,m,no2,commit);
  63. 		res+=fSegACalcAns(no*2+2,l,r,m+1,r2,no2,commit);
  64. 		return res;
  65. 	}
  66. }
  67.  
  68. long long int fSegAUpData(int no,int l,int r,int l2,int r2,int no2,int no3,bool commit){
  69. 	commit=commit && segA[no].commit;
  70. 	no3=(no3<segA[no].no)?segA[no].no:no3;
  71. 	long long int res=calc(no,no2,no3,l,r,l2,r2,commit);
  72. 	if(r2<l || r<l2)return res;
  73. 	res=calc(no,no2,no2,l,r,l2,r2,false);
  74. 	segA[no].commit=true;
  75. 	if(l2==r2){
  76. 		segA[no].no=no2;
  77. 		segA[no].num=res;
  78. 		segA[no].commit=true;
  79. 		return res;
  80. 	}
  81. 	if(l<=l2 && r2<=r){
  82. 		segA[no].no=no2;
  83. 		segA[no].num=res;
  84. 		segA[no].commit=true;
  85. 		segA[no*2+1].commit=false;
  86. 		segA[no*2+2].commit=false;
  87. 		return res;
  88. 	}else{
  89. 		int m=(l2+r2)/2;
  90. 		res=fSegAUpData(no*2+1,l,r,l2,m,no2,no3,commit);
  91. 		res+=fSegAUpData(no*2+2,l,r,m+1,r2,no2,no3,commit);
  92. 		segA[no].num=res;
  93. 		segA[no].commit=true;
  94. 		return res;
  95. 	}
  96. }
  97.  
  98. int main() {
  99. 	for(int i=0;i<maxS;i++){
  100. 		segA[i].num=0;
  101. 		segA[i].no=-1;
  102. 		segA[i].commit=true;
  103. 	}
  104. 	int n,m;
  105. 	cin>>n>>m;
  106. 	for(int i=0;i<n;i++){
  107. 		long long int num;
  108. 		cin>>num;
  109. 		fSegASet(0,i,0,R,num);
  110. 	}
  111. 	areaSum.push_back(0);
  112. 	long long int sum=0;
  113. 	for(int i=0;i<n;i++){
  114. 		long long int num;
  115. 		cin>>num;
  116. 		sum+=num;
  117. 		areaSum.push_back(sum);
  118. 	}
  119. 	for(int i=0;i<maxS;i++){
  120. 		areaSum.push_back(Sum);
  121. 	}
  122.  
  123. 	for(int i=0;i<m;i++){
  124. 		int c1,l,r,x,y,z;
  125. 		cin>>c1;
  126. 		if(c1==0){
  127. 			cin>>x>>y>>z;
  128. 			E2 e2;
  129. 			e2.l=y-1;
  130. 			e2.r=y-2+z;
  131. 			e2.x=x-1;
  132. 			e2.y=y-1;
  133. 			e2.z=z;
  134. 			l=x-1;
  135. 			r=x-2+z;
  136. 			copyData.push_back(e2);
  137. 			fSegAUpData(0,l,r,0,R,no2,-1,true);
  138. 			no2++;
  139. 		}else{
  140. 			cin>>l>>r;
  141. 			l--;
  142. 			r--;
  143. 			cout<<fSegACalcAns(0,l,r,0,R,-1,true)<<endl;
  144. 		}
  145. 		for(int i=0;i<maxS;i++){
  146. 			cout<<"("<<i<<","<<segA[i].num<<")";
  147. 		}
  148. 	cout<<endl;
  149. 	}
  150. 	return 0;
  151. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
5 5
1 3 5 7 9
2 4 6 8 10
1 1 3
1 4 5
0 4 1 2
1 1 3
1 4 5
stdout
copy 
<1 0,no2=-1,no3=-1,l=0,r=2,0,7,>
<1 1,no2=-1,no3=-1,l=0,r=2,0,3,>
<1 3,no2=-1,no3=-1,l=0,r=2,0,1,>
<1 4,no2=-1,no3=-1,l=0,r=2,2,3,>
<1 9,no2=-1,no3=-1,l=0,r=2,2,2,>
<1 10,no2=-1,no3=-1,l=0,r=2,3,3,>
<1 2,no2=-1,no3=-1,l=0,r=2,4,7,>
9
(0,25)(1,16)(2,9)(3,4)(4,12)(5,9)(6,0)(7,1)(8,3)(9,5)(10,7)(11,9)(12,0)(13,0)(14,0)(15,0)
<1 0,no2=-1,no3=-1,l=3,r=4,0,7,>
<1 1,no2=-1,no3=-1,l=3,r=4,0,3,>
<1 3,no2=-1,no3=-1,l=3,r=4,0,1,>
<1 4,no2=-1,no3=-1,l=3,r=4,2,3,>
<1 9,no2=-1,no3=-1,l=3,r=4,2,2,>
<1 10,no2=-1,no3=-1,l=3,r=4,3,3,>
<1 2,no2=-1,no3=-1,l=3,r=4,4,7,>
<1 5,no2=-1,no3=-1,l=3,r=4,4,5,>
<1 11,no2=-1,no3=-1,l=3,r=4,4,4,>
<1 12,no2=-1,no3=-1,l=3,r=4,5,5,>
<1 6,no2=-1,no3=-1,l=3,r=4,6,7,>
16
(0,25)(1,16)(2,9)(3,4)(4,12)(5,9)(6,0)(7,1)(8,3)(9,5)(10,7)(11,9)(12,0)(13,0)(14,0)(15,0)
<1 0,no2=0,no3=-1,l=3,r=4,0,7,>l3=-3,r3=5 E=25
<0 0,no2=0,no3=0,l=3,r=4,0,7,>l3=-3,r3=5 E=25
<1 1,no2=0,no3=-1,l=3,r=4,0,3,>l3=-3,r3=1 E=16
<0 1,no2=0,no3=0,l=3,r=4,0,3,>l3=-3,r3=1 E=16
<1 3,no2=0,no3=-1,l=3,r=4,0,1,>l3=-3,r3=-1 E=4
<1 4,no2=0,no3=-1,l=3,r=4,2,3,>l3=-1,r3=1 E=12
<0 4,no2=0,no3=0,l=3,r=4,2,3,>l3=-1,r3=1 E=12
<1 9,no2=0,no3=-1,l=3,r=4,2,2,>l3=-1,r3=0 E=5
<1 10,no2=0,no3=-1,l=3,r=4,3,3,>l3=0,r3=1 E=7
2 0
<0 10,no2=0,no3=0,l=3,r=4,3,3,>l3=0,r3=1 E=7
2 0
<1 2,no2=0,no3=-1,l=3,r=4,4,7,>l3=1,r3=5 E=9
30 2
<0 2,no2=0,no3=0,l=3,r=4,4,7,>l3=1,r3=5 E=9
30 2
<1 5,no2=0,no3=-1,l=3,r=4,4,5,>l3=1,r3=3 E=9
12 2
<0 5,no2=0,no3=0,l=3,r=4,4,5,>l3=1,r3=3 E=9
12 2
<1 11,no2=0,no3=-1,l=3,r=4,4,4,>l3=1,r3=2 E=9
6 2
<0 11,no2=0,no3=0,l=3,r=4,4,4,>l3=1,r3=2 E=9
6 2
<1 12,no2=0,no3=-1,l=3,r=4,5,5,>l3=2,r3=3 E=0
12 6
<1 6,no2=0,no3=-1,l=3,r=4,6,7,>l3=3,r3=5 E=0
30 12
(0,39)(1,11)(2,28)(3,4)(4,7)(5,10)(6,0)(7,1)(8,3)(9,5)(10,2)(11,4)(12,0)(13,0)(14,0)(15,0)
<1 0,no2=-1,no3=-1,l=0,r=2,0,7,>
<1 1,no2=-1,no3=-1,l=0,r=2,0,3,>
<1 3,no2=-1,no3=-1,l=0,r=2,0,1,>
<1 4,no2=-1,no3=-1,l=0,r=2,2,3,>
<1 9,no2=-1,no3=-1,l=0,r=2,2,2,>
<1 10,no2=0,no3=0,l=0,r=2,3,3,>
<1 2,no2=-1,no3=-1,l=0,r=2,4,7,>
9
(0,39)(1,11)(2,28)(3,4)(4,7)(5,10)(6,0)(7,1)(8,3)(9,5)(10,2)(11,4)(12,0)(13,0)(14,0)(15,0)
<1 0,no2=-1,no3=-1,l=3,r=4,0,7,>
<1 1,no2=-1,no3=-1,l=3,r=4,0,3,>
<1 3,no2=-1,no3=-1,l=3,r=4,0,1,>
<1 4,no2=-1,no3=-1,l=3,r=4,2,3,>
<1 9,no2=-1,no3=-1,l=3,r=4,2,2,>
<1 10,no2=0,no3=0,l=3,r=4,3,3,>
<1 2,no2=-1,no3=-1,l=3,r=4,4,7,>
<1 5,no2=-1,no3=-1,l=3,r=4,4,5,>
<1 11,no2=0,no3=0,l=3,r=4,4,4,>
<1 12,no2=-1,no3=-1,l=3,r=4,5,5,>
<1 6,no2=-1,no3=-1,l=3,r=4,6,7,>
6
(0,39)(1,11)(2,28)(3,4)(4,7)(5,10)(6,0)(7,1)(8,3)(9,5)(10,2)(11,4)(12,0)(13,0)(14,0)(15,0)
https://ideone.com/kmPEfj
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!