fork download
copy 
  1. #include<stdio.h>
  2. #include<limits.h>
  3.  
  4. void preprocess(int node,int b,int e,long long int m[],long long int a[])
  5. {
  6.      int mid;
  7. if(b == e)
  8. 	{
  9.         //printf("%d %d\n",node,b);
  10.         m[node] = a[b];}
  11. else
  12. 	{
  13. 	mid = (b+e)>>1;
  14. 	preprocess(2*node,b,mid,m,a);
  15. 	preprocess(2*node+1,mid+1,e,m,a);
  16. 	m[node]= m[2*node]+ m[2*node+1];
  17. 	}
  18. }
  19.  
  20.  
  21. void preprocess1(int node,int b,int e,long long int m[],long long int a[],int x,int y,long long int value)
  22. {
  23. if(b==e && x<=b && b<=y)
  24. m[node]+=value;
  25.  
  26. else if(b!=e)
  27. 	{
  28. 	int mid = (b+e)>>1;
  29. 		preprocess1(2*node,b,mid,m,a,x,y,value);
  30.         preprocess1(2*node+1,mid+1,e,m,a,x,y,value);
  31.         m[node] = m[2*node]+m[2*node+1];
  32. 	}
  33. }
  34.  
  35.  
  36. long long int query(int node,int b,int e,long long int m[],long long int a[],int i,int j)
  37. {
  38. int mid = (b+e)>>1;
  39. int l=0 ;
  40. int temp,p1,p2;
  41.  
  42. if(i>e || j<b)
  43. 	return l;
  44.  
  45. if(b>=i && e<=j)
  46. 	return m[node];
  47. p1 = query(2*node,b,mid,m,a,i,j);
  48. p2 = query(2*node+1,mid+1,e,m,a,i,j);
  49. return p1+p2;
  50. }	
  51.  
  52.  
  53. long long int min[600009];
  54. long long  int a[100009];
  55.  
  56.  
  57. int main()
  58. 		{
  59. 		int t,j,i,n,q1,sq,eq,ch,p,q,v3,ll;  //,*a;
  60. 		long long int pp,v; //,*min;
  61. 		char str[10],sh[2];
  62.  
  63. 	scanf("%d",&t);
  64.  
  65.  
  66.  
  67.  
  68.     while(t--){
  69.  
  70. 		scanf("%d %d",&n,&q1);
  71.  
  72. 		for(i=0;i<n;i++)
  73. 		{
  74.         a[i] = 0;
  75.         }
  76.  
  77.        	preprocess(1,0,n-1,min,a);
  78.     	for(i=0;i<q1;i++){
  79.            scanf("%d",&ll);
  80.            if(ll==0)
  81.                           {
  82.                           scanf("%d %d %lld",&p,&q,&v);
  83.                           preprocess1(1,0,n-1,min,a,p-1,q-1,v);
  84.  
  85.                           }
  86.  
  87.              if(ll==1)
  88.                             {
  89.                             scanf("%d %d",&p,&q);
  90.                             pp = (query(1,0,n-1,min,a,p-1,q-1));
  91. 	                      	printf("%lld\n",pp);
  92. 	                        }   
  93.                          } 
  94.                }
  95.  
  96.             return 0;
  97. 	}
  98.  
Success #stdin #stdout 0s 7720KB
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/Hjzd7A
language:
C (gcc 8.3)
created:
10 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!