fork download
copy 
  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<algorithm>
  6. using namespace std;
  7. long long int segtree[4100000];
  8. long long int lazy[4100000];
  9. void updatetree(int low,int high,int value,int qlow,int qhigh,int pos);
  10. long long int addtree(int low,int high,int qlow,int qhigh,int pos);
  11. int main()
  12.    {
  13.        ios::sync_with_stdio(false);
  14.        int t,b;
  15.        long long int  n,c,p,q,v,i;
  16.        cin>>t;
  17.        while(t--)
  18.        {
  19.            cin>>n>>c;
  20.            for(i=0;i<450000;i++)
  21.            {
  22.                lazy[i]=0;
  23.                segtree[i]=0;
  24.            }
  25.  
  26.            for(i=0;i<c;i++)
  27.            {
  28.             cin>>b;
  29.             if(b==0)
  30.             {
  31.                 cin>>p>>q>>v;
  32.                updatetree(0,n-1,v,p-1,q-1,0);
  33.             }
  34.            else
  35.             {
  36.                 cin>>p>>q;
  37.  
  38.                 cout<<addtree(0,n-1,p-1,q-1,0)<<"\n";
  39.             }
  40.            }
  41.        }
  42.        return 0;
  43.    }
  44.  
  45.  
  46. void updatetree(int low,int high,int value,int qlow,int qhigh,int pos)
  47.    {
  48.        if(high < qlow||low>high||qhigh<low)
  49.         return;
  50.        if(lazy[pos]!=0)                           //upadate query should contain the low & mid ranges
  51.         {
  52.             segtree[pos]+=lazy[pos];
  53.             if(low!=high)                        //verify the proof
  54.               {
  55.               lazy[2*pos+1]+=lazy[pos];
  56.               lazy[2*pos+2]+=lazy[pos];
  57.               }
  58.               lazy[pos]=0;
  59.         }
  60.  
  61.         if(qlow<=low&&qhigh>=high)
  62.         {
  63.             segtree[pos]+=value;
  64.             if(low!=high)
  65.             {
  66.                 lazy[2*pos+1]+=value;
  67.                 lazy[2*pos+2]+=value;
  68.             }
  69.           return ;
  70.         }
  71.         //if partial overlaps
  72.         long long int mid;
  73.         mid=(low+high)/2;
  74.         updatetree(low,mid,value,qlow,qhigh,2*pos+1);
  75.         updatetree(mid+1,high,value,qlow,qhigh,2+pos+2);
  76.         segtree[pos]=min(segtree[2*pos+1],segtree[2*pos+2]);
  77.    }
  78.  
  79. long long int addtree(int low,int high,int qlow,int qhigh,int pos)
  80.       {
  81.       if(qlow>high||qhigh<low||high<low||qhigh<qlow)
  82.       return 0;
  83.  
  84.       if(lazy[pos]!=0)
  85.         {
  86.         segtree[pos]+=lazy[pos];
  87.         if(low!=high)
  88.          {
  89.           lazy[2*pos+1]+=lazy[pos];
  90.           lazy[2*pos+2]+=lazy[pos];
  91.          }
  92.          lazy[pos]=0;
  93.         }
  94.  
  95.      if(qlow<=low&&qhigh>=high)
  96.      {
  97.          return segtree[pos];
  98.      }
  99.  
  100.     long long int mid=(low+high)/2;
  101.     long long int q,y;
  102.     q=addtree(low,mid,qlow,qhigh,2*pos+1);
  103.     y=addtree(mid+1,high,qlow,qhigh,2*pos+2);
  104.     return q+y;
  105.       }
  106.  
Success #stdin #stdout 0s 67456KB
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 
0
80
https://ideone.com/z2MHvN
language:
C++ (gcc 8.3)
created:
8 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!