fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define INF 999999999999999999
  5. #define MAXN 300005
  6.  
  7. struct node
  8. {
  9.     ll prop;
  10.     ll x;
  11.     ll sum;
  12. };
  13.  
  14. ll N, Q, ans;
  15. ll arr[MAXN];
  16. node tree[4 * MAXN];
  17.  
  18. void push(ll n, ll l, ll r)
  19. {
  20.     ll mid = (l + r) / 2;
  21.     ll p = tree[n].x;
  22.  
  23.     tree[n].x = 0;
  24.     tree[n].prop = 0;
  25.  
  26.     tree[2 * n].sum = (mid - l + 1) * p;
  27.     tree[2 * n + 1].sum = (r - mid) * p;
  28.  
  29.     tree[2 * n].prop = 0;
  30.     tree[2 * n].x = p;
  31.  
  32.     tree[2 * n + 1].prop = 0;
  33.     tree[2 * n + 1].x = p;
  34. }
  35.  
  36. void build(ll n, ll l, ll r)
  37. {
  38.     if(l == r)
  39.     {
  40.         tree[n].prop = 0;
  41.         tree[n].x = 0;
  42.         tree[n].sum = arr[l];
  43.         return ;
  44.     }
  45.  
  46.     ll mid = (l + r) / 2;
  47.     build(2 * n, l, mid);
  48.     build(2 * n + 1, mid + 1, r);
  49.  
  50.     tree[n].x = 0;
  51.     tree[n].prop = 0;
  52.     tree[n].sum = tree[2 * n].sum + tree[2 * n + 1].sum;
  53. }
  54.  
  55. void update_by(ll n, ll l, ll r,ll i, ll j, ll val)
  56. {
  57.     if(l > j or r < i)
  58.         return ;
  59.  
  60.     if(l != r and tree[n].x)
  61.         push(n, l, r);
  62.  
  63.     if(l >= i and r <= j)
  64.     {
  65.         tree[n].sum += (val * (r - l + 1));
  66.         tree[n].prop += val;
  67.         tree[n].x = 0;
  68.         return ;
  69.     }
  70.  
  71.     ll mid = (l + r) / 2;
  72.     update_by(2 * n, l, mid, i, j, val);
  73.     update_by(2 * n + 1, mid + 1, r, i, j, val);
  74.     tree[n].sum = tree[2 * n].sum + tree[2 * n + 1].sum + ((r - l + 1) * tree[n].prop);
  75. }
  76.  
  77. void update_to(ll n, ll l, ll r, ll i, ll j, ll val)
  78. {
  79.     if(l > j or r < i)
  80.         return ;
  81.  
  82.     if(l != r and tree[n].x)
  83.         push(n, l, r);
  84.  
  85.     if(l >= i and r <= j)
  86.     {
  87.         tree[n].prop = 0;
  88.         tree[n].x = val;
  89.         tree[n].sum = val * (r - l + 1);
  90.         return ;
  91.     }
  92.  
  93.     ll mid = (l + r) / 2;
  94.     update_to(2 * n, l, mid, i, j, val);
  95.     update_to(2 * n + 1, mid + 1, r, i, j, val);
  96.     tree[n].sum = tree[2 * n].sum + tree[2 * n + 1].sum + ((r - l + 1) * tree[n].prop);
  97. }
  98.  
  99. ll query(ll n, ll l, ll r, ll i, ll j, ll val = 0)
  100. {
  101.     if(l > j or r < i)
  102.     {
  103.         return 0;
  104.     }
  105.  
  106.     if(l != r and tree[n].x)
  107.         push(n, l, r);
  108.  
  109.     if(l >= i and r <= j)
  110.     {
  111.         return tree[n].sum + val * (r - l + 1);
  112.     }
  113.  
  114.  
  115.     ll mid = (l + r) / 2;
  116.     ll p = tree[n].prop;
  117.     ll a = query(2 * n, l, mid, i, j, val + p);
  118.     ll b = query(2 * n + 1, mid + 1, r, i, j, val + p);
  119.     return a + b;
  120. }
  121.  
  122. void solve()
  123. {
  124.     cin >> N >> Q;
  125.     for(ll i = 1; i <= N; ++ i)
  126.     {
  127.         cin >> arr[i];
  128.     }
  129.  
  130.     N = 1 << (ll) ceil(log2(N));
  131.     build(1, 1, N);
  132.  
  133.     for(ll i = 1; i <= Q; ++ i)
  134.     {
  135.         ll tt;
  136.         cin >> tt;
  137.  
  138.         if(tt == 1)
  139.         {
  140.             ll a, b, x;
  141.             cin >> a >> b >> x;
  142.             update_by(1, 1, N, a, b, x);
  143.         }
  144.         else if(tt == 2)
  145.         {
  146.             ll a, b, x;
  147.             cin >> a >> b >> x;
  148.             update_to(1, 1, N, a, b, x);
  149.         }
  150.         else
  151.         {
  152.             ll a, b;
  153.             cin >> a >> b;
  154.             cout << query(1, 1, N, a, b) << endl;
  155.         }
  156.     }
  157.     return ;
  158. }
  159.  
  160. int main()
  161. {
  162.     std::ios::sync_with_stdio(false);
  163.     std::cin.tie(nullptr);
  164.  
  165.     // freopen("input.txt","r",stdin);
  166.     // freopen("output.txt","w",stdout);
  167.  
  168.     solve();
  169.     return 0;
  170. }
  171.  
Success #stdin #stdout 0.01s 5532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1wU6WV
language:
C++ (gcc 8.3)
created:
1 year 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!