fork download
copy 
  1. #include<stdio.h>
  2.  
  3. long long lazy[500000],segmentTree[500000];
  4.  
  5.  
  6. long long query(int b,int e,int index,int i,int j)
  7. {
  8.     long long p1,p2;
  9.     if(e < i || b > j )
  10.         return 0;
  11.     if(lazy[index] != 0){
  12.  
  13.         if(b==e)
  14.             segmentTree[index] += lazy[index];
  15.         else{
  16.             segmentTree[index] += lazy[index] * (e-b+1);
  17.             lazy[index * 2 + 1] += lazy[index];
  18.             lazy[index * 2 + 2] += lazy[index];
  19.         }
  20.         lazy[index] = 0;
  21.     }
  22.  
  23.         if(b >= i && e <= j)
  24.             return segmentTree[index];
  25.         int mid = (b+e)/2;
  26.          p1  = query(b,mid,2*index+1,i,j);
  27.          p2 = query(mid+1,e,2*index + 2,i,j);
  28.         segmentTree[index] = p1+p2;
  29.         return segmentTree[index];
  30. }
  31.  
  32. void update(int b,int e,int index,long long val,int i,int j)
  33. {
  34.     int mid;
  35.  
  36.     if(b > j || e < i){
  37.       //  printf("HIIII %d %d %d %d",b,e,i,j);
  38.         return;
  39.     }
  40.  
  41.     if(lazy[index] != 0){
  42.  
  43.         if(b==e)
  44.             segmentTree[index] += lazy[index];
  45.         else{
  46.             segmentTree[index] += lazy[index] * (e-b+1);
  47.             lazy[index * 2 + 1] += lazy[index];
  48.             lazy[index * 2 + 2] += lazy[index];
  49.         }
  50.         lazy[index] = 0;
  51.     }
  52.  
  53.         if(b >= i && e <= j){
  54.             if(b==e)
  55.                 segmentTree[index] += val;
  56.             else{
  57.                 segmentTree[index] += val * (e-b+1);
  58.                 lazy[index * 2 + 1] += val;
  59.                 lazy[index * 2 + 2] += val;
  60.             }
  61.             return ;
  62.         }
  63.         mid = (b+e)/2;
  64.          update(b,mid,2*index+1,val,i,j);
  65.          update(mid+1,e,2*index + 2,val,i,j);
  66.         segmentTree[index] = query(b, mid, index * 2 + 1, b, mid) + query(mid + 1, e, index * 2 + 2, mid + 1, e);//segmentTree[index*2+1] + segmentTree[index*2+2];
  67.         //segmentTree[index] = segmentTree[index*2+1] + segmentTree[index*2+2];
  68. }
  69.  
  70.  
  71.  
  72. int main()
  73. {
  74.     int t,n,c,i,a,d,j,k;
  75.     long long value;
  76.     scanf("%d",&t);
  77.     while(t--){
  78.         scanf("%d %d", &n, &c);
  79.         for(k = 0 ; k < 500000 ; k++){
  80.             segmentTree[k] = 0;
  81.             lazy[k] = 0;
  82.         }
  83.         while(c--){
  84.             scanf("%d",&a);
  85.             if(a==0){
  86.                 scanf("%d %d %lld",&i,&j,&value);
  87.                 i = i-1;
  88.                 j = j - 1;
  89.                 update(0,n-1,0,value,i,j);//sum is just assigned no use of it.
  90.  
  91.             }
  92.             else{
  93.                 scanf("%d %d",&i,&j);
  94.                 i = i-1;
  95.                 j = j - 1;
  96.                 printf("%lld\n",query(0,n-1,0,i,j));
  97.             }
  98.         }
  99.     }
  100.     return 0;
  101. }
  102.  
  103.  
  104.  
Success #stdin #stdout 0s 9872KB
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/pVIWNd
language:
C (gcc 8.3)
created:
9 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!