fork download
copy 
  1. using namespace std;
  2. #include <bits/stdc++.h>
  3. #define S(x) scanf("%d",&x)
  4. #define S2(x,y) scanf("%d%d",&x,&y)
  5. #define wl(n) while(n--)
  6. #define ll long long
  7. #define P(x) printf("%d\n",x)
  8. #define PB push_back
  9. #define MP make_pair
  10. #define fl(i,n) for(i=0;i<n;i++)
  11. vector<int> v1;
  12. pair<int,int> p1;
  13. #define MOD 1000000007
  14. ll lazy[500001],tree[500001];
  15. void propagate(int start,int end,int index)
  16. {
  17. 	if(start!=end)
  18. 	{
  19. 		ll p=(end-start+1);
  20. 		ll val=lazy[index]/p;
  21. 		//cout<<start<<" "<<end<<" "<<val<<" "<<"pro"<<endl;
  22. 		ll q;
  23. 		if(p%2)
  24. 		 q=(ll)(p/2)+1;
  25. 		else
  26. 		 q=(ll)(p/2);
  27. 		lazy[2*index+1]=(ll)(lazy[2*index+1]+(ll)(q*val));
  28. 		p=p-q;
  29. 		lazy[2*index+2]=(ll)(lazy[2*index+2]+(ll)(p*val));
  30. 	}
  31. 	lazy[index]=0;
  32. 	return;
  33. }
  34. ll getsum(int start,int end,int q1,int q2,int index)
  35. {
  36. 	if(lazy[index]!=0)
  37. 	{
  38. 		tree[index]=(ll)(tree[index]+lazy[index]);
  39. 		propagate(start,end,index);
  40. 	}
  41. 	if(q2<start||q1>end)
  42. 		return 0;
  43. 	if(q1<=start&&q2>=end)
  44. 	{
  45. 		//cout<<start<<" "<<end<<endl;
  46. 			return tree[index];
  47. 	}
  48.  
  49. 	int mid=(start+(end-start)/2);
  50. 	ll an1=getsum(start,mid,q1,q2,2*index+1);
  51. 	ll an2=getsum(mid+1,end,q1,q2,2*index+2);
  52. 	an1=(ll)(an1+an2);
  53. 	return an1;
  54. }
  55. void update(int start,int end,int q1,int q2,int val,int index)
  56. {
  57. 	if(lazy[index]!=0)
  58. 	{
  59. 		tree[index]=(tree[index]+lazy[index]);
  60. 		//cout<<start<<" "<<end<<" "<<" up"<<endl;
  61. 		propagate(start,end,index);
  62. 	}
  63. 	if(q2<start||q1>end)
  64. 		return;
  65. 	if(q1<=start&&q2>=end)
  66. 	{
  67. 		//cout<<start<<" "<<end<<" "<<" 1up"<<endl;		
  68. 		ll int p=(end-start+1);
  69. 		tree[index]=(ll)(tree[index]+(ll)(p*val));
  70. 		lazy[index]=(lazy[index]+(ll)(p*val));
  71. 		propagate(start,end,index);
  72. 		return;
  73. 	}
  74. 	int mid=(start+(end-start)/2);
  75. 	update(start,mid,q1,q2,val,2*index+1);
  76. 	update(mid+1,end,q1,q2,val,2*index+2);
  77. 	tree[index]=(ll)(tree[2*index+1]+tree[2*index+2]);
  78. 	return;
  79. }
  80. int main()
  81. {
  82. 	//std::ios_base::sync_with_stdio(false);
  83. 	int t,n,i,j,k,m,l;
  84. 	S(t);
  85. 	int c,s,p,q,r;
  86. 	wl(t)
  87. 	{
  88. 		memset(lazy, 0, sizeof(lazy));
  89. 		memset(tree, 0, sizeof(tree));
  90. 		S2(n,c);
  91. 		wl(c)
  92. 		{
  93. 			S2(p,q);
  94. 			S(r);
  95. 			q--;
  96. 			r--;
  97. 			if(p==0)
  98. 			{
  99. 				S(s);
  100. 				update(0,n-1,q,r,s,0);
  101. 			}
  102. 			else
  103. 			{
  104. 				ll ans=(ll)(getsum(0,n-1,q,r,0));
  105. 				printf("%lld\n",ans);
  106. 			}
  107. 		}
  108.  
  109. 	}
  110. 	return 0;
  111. }
Success #stdin #stdout 0s 10960KB
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
508
https://ideone.com/6Ykdnc
language:
C++ (gcc 8.3)
created:
9 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!