SHARE
TWEET

Untitled

Arrias Dec 12th, 2018 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define mp make_pair  
  7.  
  8. ll const N = 100005;
  9.  
  10. struct Tree
  11. {
  12.     ll add = -1, sum = 0, tl, tr;
  13. } t[4 * N];
  14.  
  15. void push(ll i)
  16. {
  17.     if (t[i].add != -1) {
  18.         if (t[i].tl + 1 == t[i].tr) {
  19.             t[i].sum = t[i].add;
  20.         }
  21.         else {
  22.             t[i].sum = (t[i].tr - t[i].tl) * t[i].add;
  23.             t[i * 2].add = t[i].add;
  24.             t[i * 2 + 1].add = t[i].add;
  25.         }
  26.     }
  27.     t[i].add = -1;
  28. }
  29.  
  30. void build(ll i, ll l, ll r)
  31. {
  32.     t[i].tl = l, t[i].tr = r;
  33.     if (l + 1 == r) {
  34.         return;
  35.     }
  36.     build(i * 2, l, (l + r) / 2);
  37.     build(i * 2 + 1, (l + r) / 2, r);
  38. }
  39.  
  40. void update(ll i, ll l, ll r, ll x)
  41. {
  42.     push(i);
  43.     if (l <= t[i].tl && t[i].tr <= r) {
  44.         t[i].add = x;
  45.         push(i);
  46.         return;
  47.     }
  48.     else if (t[i].tr <= l || t[i].tl >= r) {
  49.         return;
  50.     }
  51.     update(i * 2, l, r, x);
  52.     update(i * 2 + 1, l, r, x);
  53.     t[i].sum = t[i * 2].sum + t[i * 2 + 1].sum;
  54. }
  55.  
  56. ll get(ll i, ll l, ll r)
  57. {
  58.     push(i);
  59.     if (l <= t[i].tl && t[i].tr <= r) {
  60.         return t[i].sum;
  61.     }
  62.     else if (t[i].tr <= l || t[i].tl >= r) {
  63.         return 0;
  64.     }
  65.     return get(i * 2, l, r) + get(i * 2 + 1, l, r);
  66. }
  67.  
  68. int main()
  69. {
  70.     freopen("sum.in", "r", stdin);
  71.     freopen("sum.out", "w", stdout);
  72.     ll n, k;
  73.     cin >> n >> k;
  74.     build(1, 0, n);
  75.     while (k--) {
  76.         char tt;
  77.         cin >> tt;
  78.         if (tt == 'A') {
  79.             ll l, r, z;
  80.             cin >> l >> r >> z;
  81.             update(1, l - 1, r, z);
  82.         }
  83.         else {
  84.             ll l, r;
  85.             cin >> l >> r;
  86.             cout << get(1, l - 1, r) << '\n';
  87.         }
  88.     }
  89.     return 0;
  90. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top