fork download
copy 
  1. /*#include<iostream>
  2. #include<string>
  3. #include<vector>
  4. #include<array>
  5. #include<queue>
  6. #include<stack>
  7. #include<algorithm>*/
  8. #include<bits/stdc++.h>
  9. using namespace std;
  10.  
  11. #define all(x) x.begin(), x.end()
  12.  
  13. using i64 = long long;
  14. using f64 = double;
  15. using vi = vector<i64>;
  16.  
  17. constexpr char nl = '\n';
  18. constexpr i64 N = 1e5;
  19. constexpr f64 err = 1e-6;
  20. constexpr int INF = 2e9;
  21.  
  22. struct Lazy
  23. {
  24.     struct Node
  25.     {
  26.         i64 sum = 0;
  27.         int replace = INF;
  28.         i64 add = 0;
  29.     };
  30.  
  31.     int n;
  32.     vector<Node> tree;
  33.  
  34.     Lazy(vector<int> const& v)
  35.     {
  36.         n = v.size();
  37.         tree.resize(4*n);
  38.         build(1, 0, n, v);
  39.     }
  40.  
  41.     Node Op(Node const& x, Node const& y)
  42.     {
  43.         return {x.sum + y.sum, INF, 0};
  44.     }
  45.  
  46.     #define LC i << 1
  47.     #define RC i << 1 | 1
  48.     #define MD (l + r) / 2
  49.  
  50.     void build(int i, int l, int r, vector<int> const& v)
  51.     {
  52.         if(l+1 == r)
  53.         {
  54.             tree[i].sum = v[l];
  55.             return;
  56.         }
  57.  
  58.         build(LC, l, MD, v);
  59.         build(RC, MD, r, v);
  60.         tree[i] = Op(tree[LC], tree[RC]);
  61.     }
  62.  
  63.     void push(int i, int l, int r)
  64.     {
  65.         if(tree[i].replace != INF)
  66.         {
  67.             tree[LC].sum = 1LL * tree[i].replace * (MD - l);
  68.             tree[RC].sum = 1LL * tree[i].replace * (r - MD);
  69.  
  70.             tree[LC].replace = tree[RC].replace = tree[i].replace;
  71.             tree[LC].add = tree[RC].add = 0;
  72.  
  73.             tree[i].replace = INF;
  74.         }
  75.  
  76.         tree[LC].sum += tree[i].add * (MD - l);
  77.         tree[RC].sum += tree[i].add * (r - MD);
  78.  
  79.         tree[LC].add += tree[i].add;
  80.         tree[RC].add += tree[i].add;
  81.  
  82.         tree[i].add = 0;
  83.     }
  84.  
  85.     void upd(int i, int l, int r, int lo, int hi, int v, bool fl)
  86.     {
  87.         if(l == lo && r == hi)
  88.         {
  89.             if(fl)
  90.             {
  91.                 tree[i].sum += 1LL * v * (r - l);
  92.                 tree[i].add += v;
  93.             }
  94.             else
  95.             {
  96.                 tree[i].sum = 1LL *     v * (r - l);
  97.                 tree[i].replace = v;
  98.                 tree[i].add = 0;
  99.             }
  100.  
  101.             return;
  102.         }
  103.  
  104.         push(i, l, r);
  105.  
  106.         if(hi <= MD)
  107.             upd(LC, l,  MD, lo, hi, v, fl);
  108.         else if(MD <= lo)
  109.             upd(RC, MD, r, lo, hi, v, fl);
  110.         else
  111.         {
  112.             upd(LC, l, MD, lo, MD, v, fl);
  113.             upd(RC, MD, r, MD, hi, v, fl);
  114.         }
  115.  
  116.         tree[i] = Op(tree[LC], tree[RC]);
  117.     }
  118.  
  119.     Node ask(int i, int l, int r, int lo, int hi)
  120.     {
  121.         if(l == lo && r == hi)
  122.             return tree[i];
  123.  
  124.         push(i, l, r);
  125.  
  126.         if(hi <= MD)
  127.             return ask(LC, l, MD, lo, hi);
  128.         else if(MD <= lo)
  129.             return ask(RC, MD, r, lo, hi);
  130.         return Op(ask(LC, l, MD, lo, MD), ask(RC, MD, r, MD, hi));
  131.     }
  132.  
  133.     #undef LC
  134.     #undef RC
  135.     #undef MD
  136.  
  137.     void upd(int l, int r, int v, bool fl)
  138.     {
  139.         upd(1, 0, n, l, r, v, fl);
  140.     }
  141.  
  142.     i64 ask(int l, int r)
  143.     {
  144.         return ask(1, 0, n, l, r).sum;
  145.     }
  146. };
  147.  
  148. void solve()
  149. {
  150.     int n, q;
  151.     cin >> n >> q;
  152.  
  153.     vector<int> v(n);
  154.     for(auto&& i : v)
  155.         cin >> i;
  156.  
  157.     Lazy tree(v);
  158.  
  159.     while(q--)
  160.     {
  161.         int t, l, r, x;
  162.         cin >> t >> l >> r;
  163.         --l, --r;
  164.  
  165.         if(t == 1)
  166.         {
  167.             cin >> x;
  168.             tree.upd(l, r+1, x, true);
  169.         }
  170.         else if(t == 2)
  171.         {
  172.             cin >> x;
  173.             tree.upd(l, r+1, x, false);
  174.         }
  175.         else
  176.             cout << tree.ask(l, r+1) << nl;
  177.     }    
  178. }
  179.  
  180. int main()
  181. {
  182.     ios_base::sync_with_stdio(false), cin.tie(nullptr);
  183.  
  184.     int t = 1;
  185.     // cin >> t;
  186.     for(int i = 1; i <= t; ++i)
  187.     {
  188.         solve();
  189.     }
  190. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
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
copy 
7
11
15
https://ideone.com/HvzqGQ
language:
C++14 (gcc 8.3)
created:
1 day 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!