fork download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5.  
  6. struct SegmentTreeNode 
  7. {
  8.     ll sum = 0;
  9.     void assignLeaf(ll value) 
  10.     {
  11.         sum = value;
  12.     }
  13.  
  14.     void merge(SegmentTreeNode& left, SegmentTreeNode& right) 
  15.     {
  16.         sum = left.sum + right.sum;
  17.     }
  18.  
  19.     ll getValue() 
  20.     {
  21.         return sum;
  22.     }
  23. };
  24.  
  25. class SegmentTree 
  26. {
  27.     SegmentTreeNode* nodes;
  28.     int N;
  29.     vector<ll> lazy;
  30.     public:
  31.  
  32.     SegmentTree(ll arr[], int N) 
  33.     {
  34.         this->N = N;
  35.         nodes = new SegmentTreeNode[4*N+1];
  36.         lazy.resize(4*N+1,0);
  37.         buildTree(arr, 1, 0, N-1);
  38.     }
  39.  
  40.     ~SegmentTree() 
  41.     {
  42.         delete[] nodes;
  43.     }
  44.  
  45.     ll getValue(int lo, int hi) 
  46.     {
  47.         SegmentTreeNode result = getValue(1, 0, N-1, lo, hi);
  48.         return result.getValue();
  49.     }
  50.  
  51.     void update(int index, ll value)
  52.     {
  53.         update(1, 0, N-1, index, value);
  54.     }
  55.  
  56.  
  57.     void buildTree(ll arr[], int stIndex, int lo, int hi) 
  58.     {
  59.         if (lo == hi) 
  60.         {
  61.             nodes[stIndex].assignLeaf(arr[lo]);
  62.             return;
  63.         }
  64.         int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;
  65.         buildTree(arr, left, lo, mid);
  66.         buildTree(arr, right, mid + 1, hi);
  67.         nodes[stIndex].merge(nodes[left], nodes[right]);
  68.     }
  69.  
  70.     SegmentTreeNode getValue(int stIndex, int left, int right, int lo, int hi) 
  71.     {
  72.         if (left == lo && right == hi)
  73.         return nodes[stIndex];
  74.  
  75.         int mid = (left + right) / 2;
  76.         if (lo > mid)
  77.         return getValue(2*stIndex+1, mid+1, right, lo, hi);
  78.         if (hi <= mid)
  79.         return getValue(2*stIndex, left, mid, lo, hi);
  80.  
  81.         SegmentTreeNode leftResult = getValue(2*stIndex, left, mid, lo, mid);
  82.         SegmentTreeNode rightResult = getValue(2*stIndex+1, mid+1, right, mid+1, hi);
  83.         SegmentTreeNode result;
  84.         result.merge(leftResult, rightResult);
  85.         return result;
  86.     }
  87.  
  88.     int getSegmentTreeSize(int N) 
  89.     {
  90.         int size = 1;
  91.         for (; size < N; size <<= 1);
  92.         return size << 1;
  93.     }
  94.  
  95.     void update(int stIndex, int lo, int hi, int index, ll value) 
  96.     {
  97.         if (lo == hi) 
  98.         {
  99.             nodes[stIndex].assignLeaf(value);
  100.             return;
  101.         }
  102.  
  103.         int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;
  104.         if (index <= mid)
  105.         update(left, lo, mid, index, value);
  106.         else
  107.         update(right, mid+1, hi, index, value);   
  108.         nodes[stIndex].merge(nodes[left], nodes[right]);
  109.     }
  110.  
  111.     void lazy_update(int a, int b, int start, int end, int index, ll val)
  112.     {
  113.         if(lazy[index] != 0)
  114.         {
  115.             nodes[index].sum += (end-start+1)*lazy[index];
  116.             if(start != end)
  117.             {
  118.                 lazy[2*index] += lazy[index];
  119.                 lazy[2*index+1] += lazy[index];
  120.             }            
  121.             lazy[index] = 0;
  122.         }
  123.         if(b < start || a > end) return;
  124.  
  125.         if(a <= start && b >= end)
  126.         {
  127.             nodes[index].sum += (end-start+1)*val;
  128.             if(start != end)
  129.             {
  130.                 lazy[2*index] += val;
  131.                 lazy[2*index+1] += val;
  132.             }
  133.             return;
  134.         }
  135.  
  136.         else
  137.         {
  138.             int mid = (start+end)/2;
  139.             lazy_update(a,b,start,mid,2*index,val);
  140.             lazy_update(a,b,mid+1,end,2*index+1,val);
  141.             nodes[index].sum = nodes[2*index].sum + nodes[2*index+1].sum;
  142.         }
  143.     }
  144.  
  145.     ll lazy_query(int a, int b, int start,int end, int index)
  146.     {
  147.         if(b < start || a > end) return 0;
  148.  
  149.         if(lazy[index] != 0)
  150.         {
  151.             nodes[index].sum += (end-start+1)*lazy[index];
  152.             if(start != end)
  153.             {
  154.                 lazy[2*index] += lazy[index];
  155.                 lazy[2*index+1] += lazy[index];
  156.             }            
  157.             lazy[index] = 0;
  158.         }
  159.  
  160.         if(a <= start && b >= end)
  161.         {
  162.             return nodes[index].sum;
  163.         }
  164.  
  165.         else
  166.         {
  167.             int mid = (start+end)/2;
  168.             ll l = lazy_query(a,b,start,mid,2*index);
  169.             ll r = lazy_query(a,b,mid+1,end,2*index+1);
  170.             return l+r;
  171.         }
  172.     }
  173. };
  174.  
  175. int main()
  176. {
  177.     ios_base::sync_with_stdio(false);
  178.     cin.tie(NULL);
  179.     int t;
  180.     cin>>t;
  181.     while(t--)
  182.     {
  183.         int n,c;
  184.         cin>>n>>c;
  185.         ll arr[n];
  186.         for(int i=0; i<n; ++i) arr[i] = 0;
  187.         SegmentTree st(arr,n);
  188.         while(c--)
  189.         {
  190.             int x;
  191.             cin>>x;
  192.             if(x == 0)
  193.             {
  194.                 int a,b;
  195.                 ll value;
  196.                 cin>>a>>b>>value;
  197.                 st.lazy_update(a-1,b-1,0,n-1,1,value);
  198.             }
  199.             else
  200.             {
  201.                 int a,b;
  202.                 cin>>a>>b;
  203.                 cout << st.lazy_query(a-1,b-1,0,n-1,1) <<"\n";
  204.             }
  205.         }
  206.     }
  207.     return 0;
  208. }
Success #stdin #stdout 0s 15248KB
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/gjnhea
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 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!