fork(2) download 
  1. /*
  2.     author: kartik8800
  3. */
  4. #include<bits/stdc++.h>
  5. #define ll long long
  6. #define pb push_back
  7. #define fr(a,b) for(ll i = a; i < b; i++)
  8. #define mod 1000000007
  9. #define inf (1LL<<60)
  10. #define all(x) (x).begin(), (x).end()
  11. #define prDouble(x) cout << fixed << setprecision(10) << x
  12. #define triplet pair<ll,pair<ll,ll>>
  13. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  14. using namespace std;
  15.  
  16. struct node
  17. {
  18.     ll sum;
  19.     ll setAll;
  20.     ll increment;
  21.     bool setAllValid;
  22.     node()
  23.     {
  24.        sum = 0;
  25.        setAllValid = 0;
  26.        increment = 0;
  27.     }
  28.     void Reset()
  29.     {
  30.        setAllValid = increment = 0;
  31.     }
  32. };
  33.  
  34. class segtree
  35. {
  36.     int range;
  37.     vector<node> tree;
  38. public:
  39.     void build(vector<int>& v)
  40.     {
  41.         range = v.size();
  42.         tree.assign(4*range, node());
  43.         build_recur(v, 0, range-1, 0);
  44.     }
  45.     void build_recur(vector<int>& v, int l, int r, int node_no)
  46.     {
  47.         if(l == r){
  48.             if(l < v.size())
  49.                 tree[node_no].sum = v[l];
  50.             else tree[node_no].sum = 0;
  51.             return;
  52.         }
  53.         int mid = (l+r)/2;
  54.         build_recur(v, l, mid, 2*node_no + 1);
  55.         build_recur(v, mid + 1, r, 2*node_no + 2);
  56.         tree[node_no].sum = tree[2*node_no + 1].sum + tree[2*node_no + 2].sum;
  57.     }
  58.     ll range_query(int L, int R)
  59.     {
  60.         return range_query_recur(0, 0, range - 1, L, R);
  61.     }
  62.  
  63.     void incUpdate_recur(int node, int l, int r, int& L, int& R, int& X)
  64.     {
  65.         if(r < L || R < l || l >= range)
  66.             return;
  67.         if(L <= l && R >= r)
  68.         {
  69.             tree[node].increment += X;
  70.             return;
  71.         }
  72.         applyAggr(node,l,r);
  73.         int mid = (l+r)/2;
  74.         incUpdate_recur(2*node+1,l,mid,L,R,X);
  75.         incUpdate_recur(2*node+2,mid+1,r,L,R,X);
  76.         applyAggr(2*node+1, l, mid);
  77.         applyAggr(2*node+2, mid+1, r);
  78.         tree[node].sum = tree[2*node+1].sum + tree[2*node+2].sum;
  79.     }
  80.  
  81.     void incUpdate(int L, int R, int X)
  82.     {
  83.         incUpdate_recur(0,0,range-1,L,R,X);
  84.     }
  85.  
  86.     void setUpdate_recur(int node, int l, int r, int& L, int& R, int& X)
  87.     {
  88.         if(r < L || R < l || l >= range)
  89.             return;
  90.         if(L <= l && R >= r)
  91.         {
  92.             tree[node].setAllValid = 1;
  93.             tree[node].setAll = X;
  94.             tree[node].increment = 0;
  95.             return;
  96.         }
  97.         applyAggr(node,l,r);
  98.         int mid = (l+r)/2;
  99.         setUpdate_recur(2*node+1,l,mid,L,R,X);
  100.         setUpdate_recur(2*node+2,mid+1,r,L,R,X);
  101.         applyAggr(2*node+1, l, mid);
  102.         applyAggr(2*node+2, mid+1, r);
  103.         tree[node].sum = tree[2*node+1].sum + tree[2*node+2].sum;
  104.     }
  105.  
  106.     void setUpdate(int L, int R, int X)
  107.     {
  108.         setUpdate_recur(0,0,range-1,L,R,X);
  109.     }
  110.  
  111.     void compose(int par, int child)
  112.     {
  113.         if(tree[par].setAllValid){
  114.             tree[child].setAllValid = 1;
  115.             tree[child].setAll = tree[par].setAll;
  116.             tree[child].increment = tree[par].increment;
  117.         }
  118.         else tree[child].increment += tree[par].increment;
  119.     }
  120.  
  121.     void applyAggr(int node, int l, int r)
  122.     {
  123.         if(tree[node].setAllValid)
  124.             tree[node].sum = (r-l+1)*tree[node].setAll;
  125.  
  126.         tree[node].sum += (r-l+1)*tree[node].increment;
  127.  
  128.         if(l != r){
  129.             compose(node, 2*node + 1);
  130.             compose(node, 2*node + 2);
  131.         }
  132.  
  133.         tree[node].Reset();
  134.     }
  135.  
  136.     ll range_query_recur(int node, int l, int r, int& L, int& R)
  137.     {
  138.         if(r < L || R < l || l >= range)
  139.             return 0;
  140.         applyAggr(node, l, r);
  141.         if(L <= l && R >= r)
  142.             return tree[node].sum;
  143.         int mid = (l+r)/2;
  144.         return range_query_recur(2*node + 1, l, mid, L, R) + range_query_recur(2*node + 2, mid+1, r, L, R);
  145.     }
  146. };
  147.  
  148. int main() {
  149.    fast_io;
  150.    int n,q;
  151.    cin >> n >> q;
  152.  
  153.    vector<int> v(n);
  154.    for(int i = 0; i < n; i++)
  155.         cin >> v[i];
  156.  
  157.    segtree sg;
  158.    sg.build(v);
  159.  
  160.    while(q--)
  161.    {
  162.         int t;
  163.         cin >> t;
  164.         if(t == 1){
  165.             int a,b,x;
  166.             cin >> a >> b >> x;
  167.             sg.incUpdate(a-1,b-1,x);
  168.         }
  169.         else if(t == 2){
  170.             int a,b,x;
  171.             cin >> a >> b >> x;
  172.             sg.setUpdate(a-1,b-1,x);
  173.         }
  174.         else {
  175.             int a,b;
  176.             cin >> a >> b;
  177.             cout << sg.range_query(a-1,b-1) <<'\n';
  178.         }
  179.    }
  180.    return 0;
  181. }
  182.  
Success #stdin #stdout 0s 4564KB
comments (?)
stdin 
6 5
2 3 1 1 5 3
3 3 5
1 2 4 2
3 3 5
2 2 4 5
3 3 5
stdout 
7
11
15
https://ideone.com/8HQxMk
language:
C++14 (gcc 8.3)
created:
4 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!