fork download
copy 
  1. /*  includes    */
  2. #include <bits/stdc++.h>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. /*__________________________________________*/
  6.  
  7. /*  defines     */
  8. #define ll long long
  9. #define ACCEPTED 0
  10. #define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  11. #define all(x) x.begin(), x.end()
  12. #define multihash array<ll, B>
  13. /*__________________________________________*/
  14.  
  15. /*  ordered set  */
  16. using namespace std;
  17. using namespace __gnu_pbds;
  18. template <typename T>
  19. using ordered_set = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
  20. template <typename t>
  21. using ordered_multiset = tree<t, null_type, less_equal<t>, rb_tree_tag, tree_order_statistics_node_update>;
  22. /*__________________________________________*/
  23.  
  24. /*  constants  */
  25. const long long mod = 1e9 + 7;
  26. const long long INF = 1e18;
  27. const ll N = 2e6 + 5;
  28. /*__________________________________________*/
  29. vector<ll> lazySum;
  30. vector<ll> lazySet;
  31. vector<ll> sum;
  32. vector<ll> vec;
  33. ll SQ;
  34. ll n, q;
  35. void build(ll idx)
  36. {
  37.     if (lazySet[idx / SQ] == 0 && lazySum[idx / SQ] == 0)
  38.     {
  39.         return;
  40.     }
  41.     for (int i = (idx / SQ) * SQ; i < ((idx / SQ) * SQ) + SQ && i < n; i++)
  42.     {
  43.         if (lazySet[i / SQ] != 0)
  44.         {
  45.             vec[i] = lazySet[i / SQ];
  46.         }
  47.         vec[i] += lazySum[i / SQ];
  48.     }
  49.     lazySet[idx / SQ] = 0;
  50.     lazySum[idx / SQ] = 0;
  51. }
  52. signed main()
  53. {
  54.     fastIO;
  55.     cin >> n >> q;
  56.     SQ = sqrt(n) + 2;
  57.     vec.resize(n);
  58.     lazySum.resize(SQ, 0);
  59.     lazySet.resize(SQ, 0);
  60.     sum.resize(SQ, 0);
  61.  
  62.     for (ll i = 0; i < n; i++)
  63.     {
  64.         cin >> vec[i];
  65.         sum[i / SQ] += vec[i];
  66.     }
  67.     while (q--)
  68.     {
  69.         ll op;
  70.         cin >> op;
  71.         ll a, b;
  72.         cin >> a >> b;
  73.         a--, b--;
  74.         if (op == 1)
  75.         {
  76.             ll x;
  77.             cin >> x;
  78.             if (a % SQ != 0)
  79.             {
  80.                 build(a);
  81.             }
  82.             build(b);
  83.  
  84.             for (int i = a; i <= b;)
  85.             {
  86.                 if (i % SQ == 0 && i + SQ - 1 <= b)
  87.                 {
  88.                     lazySum[i / SQ] += x;
  89.                     sum[i / SQ] += x * SQ;
  90.                     i += SQ;
  91.                 }
  92.                 else
  93.                 {
  94.                     sum[i / SQ] += x;
  95.                     vec[i] += x;
  96.                     i++;
  97.                 }
  98.             }
  99.         }
  100.         else if (op == 2)
  101.         {
  102.             ll x;
  103.             cin >> x;
  104.             if (a % SQ != 0)
  105.             {
  106.                 build(a);
  107.             }
  108.             build(b);
  109.             for (int i = a; i <= b;)
  110.             {
  111.                 if (i % SQ == 0 && i + SQ - 1 <= b)
  112.                 {
  113.                     lazySum[i / SQ] = 0;
  114.                     lazySet[i / SQ] = x;
  115.                     sum[i / SQ] = x * SQ;
  116.                     i += SQ;
  117.                 }
  118.                 else
  119.                 {
  120.                     sum[i / SQ] -= vec[i];
  121.                     vec[i] = x;
  122.                     sum[i / SQ] += vec[i];
  123.                     i++;
  124.                 }
  125.             }
  126.         }
  127.         else
  128.         {
  129.             ll ans = 0;
  130.             if (a % SQ != 0)
  131.             {
  132.                 build(a);
  133.             }
  134.             build(b);
  135.             for (int i = a; i <= b;)
  136.             {
  137.                 if (i % SQ == 0 && i + SQ - 1 <= b)
  138.                 {
  139.                     ans += sum[i / SQ];
  140.                     i += SQ;
  141.                 }
  142.                 else
  143.                 {
  144.                     ans += vec[i];
  145.                     i++;
  146.                 }
  147.             }
  148.             cout << ans << "\n";
  149.         }
  150.     }
  151.  
  152.     return ACCEPTED;
  153. }
  154.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Yb8V4m
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!