fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long tree[400000],lazy[400000];
  4. int co[400000];
  5. void update(int node,int s,int e,int p,int q)
  6. {
  7. 	if(co[node]!=0)
  8. 	{
  9. 		//printf("!%d ",lazy[node]);
  10. 		tree[node]+=lazy[node]*(e-s+1)+co[node]*(((e-s+2)*(e-s+1)))/2;
  11. 		//printf("[%d]=%lld ",node,tree[node]);
  12. 		if(s!=e)
  13. 		{
  14. 			lazy[node*2+1]+=lazy[node];
  15. 			co[node*2+1]+=co[node];
  16. 			lazy[node*2+2]+=lazy[node]+((s+e)/2-s+1);
  17. 			co[node*2+2]+=co[node];
  18. 			//printf("L[%d]=%lld L[%d]=%lld ",node*2+1,lazy[node*2+1],node*2+2,lazy[node*2+2]);
  19. 			//printf("C[%d]=%d C[%d]=%d ",node*2+1,co[node*2+1],node*2+2,co[node*2+2]);
  20. 		}
  21. 		lazy[node]=0;
  22. 		co[node]=0;
  23. 	}
  24. 	if(s>e||p>e||q<s)
  25. 	return;
  26. 	if(p<=s&&q>=e)
  27. 	{
  28. 		//printf("PP ");
  29. 		long long st=s-p+1;
  30. 		tree[node]+=st*(e-s+1)+((e-s)*(e-s+1))/2;
  31. 		//printf("[%d]=%lld ",node,tree[node]);
  32. 		if(s!=e)
  33. 		{
  34. 			lazy[node*2+1]+=st-1;
  35. 			co[node*2+1]+=1;
  36. 			lazy[node*2+2]+=st+((s+e)/2-s);
  37. 			co[node*2+2]+=1;
  38. 			//printf("L[%d]=%lld L[%d]=%lld ",node*2+1,lazy[node*2+1],node*2+2,lazy[node*2+2]);
  39. 			//printf("C[%d]=%d C[%d]=%d ",node*2+1,co[node*2+1],node*2+2,co[node*2+2]);
  40. 		}
  41. 		return ;
  42. 	}
  43. 	int mid=(s+e)/2;
  44. 	update(node*2+1,s,mid,p,q);
  45. 	update(node*2+2,mid+1,e,p,q);
  46. 	tree[node]=tree[node*2+1]+tree[node*2+2];
  47. 	//printf("[%d]=%lld \n",node,tree[node]);
  48. }
  49. long long query(int node,int s,int e,int p,int q)
  50. {
  51. 	if(s>e||p>e||q<s)
  52. 	return 0;
  53. 	if(co[node]!=0)
  54. 	{
  55. 		tree[node]+=lazy[node]*(e-s+1)+co[node]*(((e-s+2)*(e-s+1)))/2;
  56. 		if(s!=e)
  57. 		{
  58. 			lazy[node*2+1]+=lazy[node];
  59. 			co[node*2+1]+=co[node];
  60. 			lazy[node*2+2]+=lazy[node]+((s+e)/2-s+1);
  61. 			co[node*2+2]+=co[node];
  62. 		}
  63. 		lazy[node]=0;
  64. 		co[node]=0;
  65. 	}
  66. 	if(p<=s&&q>=e)
  67. 	return tree[node];
  68. 	int mid=(s+e)/2;
  69. 	return query(node*2+1,s,mid,p,q)+query(node*2+2,mid+1,e,p,q);
  70. }
  71. int main()
  72. {
  73. 	int n,q,i,p,q1,c;
  74. 	scanf("%d%d",&n,&q);
  75. 	memset(tree,0,sizeof tree);
  76. 	memset(lazy,0,sizeof lazy);
  77. 	memset(co,0,sizeof co);
  78. 	for(i=0;i<q;i++)
  79. 	{
  80. 		scanf("%d%d%d",&c,&p,&q1);
  81. 		if(c==0)
  82. 		update(0,0,n-1,p-1,q1-1);
  83. 		else
  84. 		printf("%lld\n",query(0,0,n-1,p-1,q1-1));
  85. 	}
  86. 	return 0;
  87. }
Success #stdin #stdout 0s 23056KB
comments (?)
stdin
copy 
7 24
0 2 2
0 1 7              
0 1 5
0 2 4
0 4 7
0 4 6
0 3 5
0 2 3
0 1 7
0 3 3
1 5 5
1 1 6
1 3 5
0 2 2
0 1 7              
0 1 5
0 2 4
0 4 7
0 4 6
0 3 5
0 2 3
0 1 7
0 3 3
1 5 5
stdout
copy 
22
84
55
44
https://ideone.com/LcGbrb
language:
C++ (gcc 8.3)
created:
6 years 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!