fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/tree_policy.hpp>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4.  
  5. #define ll long long
  6. #define ld long double
  7. #define el "\n"
  8. using namespace __gnu_pbds;
  9. using namespace std;
  10.  
  11. template <typename T>
  12. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  13.  
  14. const int N = 2e5 + 5, LOG = 22, mod = 998244353, SQ = 350;
  15. const ld pi = acos(-1);
  16. const ld eps = 1e-4;
  17. int dx[] = {0, -1, 0, 1, -1, 1, -1, 1};
  18. int dy[] = {-1, 0, 1, 0, 1, -1, -1, 1};
  19. int n;
  20. ll a[N];
  21. ll sum[N / SQ + 5], lazy[N / SQ + 5];
  22. bool del[N / SQ + 5];
  23.  
  24. void build(int buc_num)
  25. {
  26.     sum[buc_num] = 0;
  27.     for (int i = buc_num * SQ; i < min(buc_num * SQ + SQ, n); i++)
  28.     {
  29.         if (del[buc_num])
  30.         {
  31.             a[i] = lazy[i / SQ];
  32.         }
  33.         else
  34.         {
  35.             a[i] += lazy[i / SQ];
  36.         }
  37.         sum[buc_num] += a[i];
  38.     }
  39.     lazy[buc_num] = 0;
  40.     del[buc_num] = 0;
  41. }
  42.  
  43. void update(int op, int l, int r, int val)
  44. {
  45.     build(l / SQ);
  46.     build(r / SQ);
  47.     for (int i = l; i <= r;)
  48.     {
  49.         if (i % SQ == 0 && i + SQ - 1 <= r)
  50.         {
  51.             if (op == 1)
  52.             {
  53.                 lazy[i / SQ] += val;
  54.             }
  55.             else
  56.             {
  57.                 lazy[i / SQ] = val;
  58.                 sum[i / SQ] = 0;
  59.                 del[i / SQ] = 1;
  60.             }
  61.             i += SQ;
  62.         }
  63.         else
  64.         {
  65.             int prv = a[i];
  66.             if (op == 1)
  67.             {
  68.                 a[i] += val;
  69.             }
  70.             else
  71.             {
  72.                 a[i] = val;
  73.             }
  74.             sum[i / SQ] = sum[i / SQ] - prv + a[i];
  75.             i++;
  76.         }
  77.     }
  78. }
  79.  
  80. ll query(int l, int r)
  81. {
  82.     build(l / SQ);
  83.     build(r / SQ);
  84.     ll ans = 0;
  85.     for (int i = l; i <= r;)
  86.     {
  87.         if (i % SQ == 0 && i + SQ - 1 <= r)
  88.         {
  89.             ans += (sum[i / SQ] + lazy[i / SQ] * 1LL * SQ);
  90.             i += SQ;
  91.         }
  92.         else
  93.         {
  94.             ans += a[i];
  95.             i++;
  96.         }
  97.     }
  98.     return ans;
  99. }
  100.  
  101. void dowork()
  102. {
  103.     int q, op, l, r, val;
  104.     cin >> n >> q;
  105.     for (int i = 0; i < n; i++)
  106.     {
  107.         cin >> a[i];
  108.     }
  109.     for (int i = 0; i < n; i += SQ)
  110.     {
  111.         build(i / SQ);
  112.     }
  113.     while (q--)
  114.     {
  115.         cin >> op >> l >> r;
  116.         l--;
  117.         r--;
  118.         if (op <=2)
  119.         {
  120.             cin >> val;
  121.             update(op, l, r, val);
  122.         }
  123.         else
  124.         {
  125.             cout << query(l, r) << el;
  126.         }
  127.     }
  128. }
  129.  
  130. signed main()
  131. {
  132.     ios_base::sync_with_stdio(0);
  133.     cin.tie(0);
  134.     cout.tie(0);
  135. #ifndef ONLINE_JUDGE
  136.     freopen("input.txt", "r", stdin);
  137.     freopen("output.txt", "w", stdout);
  138. #endif
  139.     int t = 1;
  140.     // cin >> t;
  141.     for (int i = 1; i <= t; i++)
  142.     {
  143.         dowork();
  144.     }
  145.     return 0;
  146. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gWc7jx
language:
C++14 (gcc 8.3)
created:
11 days 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!