Advertisement
Guest User

Untitled

a guest
Sep 15th, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.78 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <bits/stdc++.h>
  3.  
  4. #define all(x) begin(x), end(x)
  5. #define rall(x) rbegin(x), rend(x)
  6.  
  7. #define file "sum"
  8.  
  9. using namespace std;
  10. using ll = long long;
  11. using ull = unsigned long long;
  12. using str = string;
  13. using srt = short;
  14.  
  15. const int INF = (int)1e9 + 7;
  16. const int MOD = 998244353;
  17. const ll inf = (ll)2e18;
  18. const ll mod = (int)1e9 + 7;
  19. const int N = 1000 + 5;
  20.  
  21. int n, m;
  22. vector<int> tree;
  23.  
  24. void push(int v)
  25. {
  26.     if (tree[v] != -1)
  27.     {
  28.         tree[v * 2] = tree[v * 2 + 1] = tree[v];
  29.         tree[v] = -1;
  30.     }
  31. }
  32.  
  33. void upd(int l, int r, int x, int v = 1, int tl = 0, int tr = n - 1)
  34. {
  35.     if (l > r)
  36.         return;
  37.     if (tl == l && tr == r)
  38.     {
  39.         tree[v] = x;
  40.         return;
  41.     }
  42.     int tm = tl + tr >> 1;
  43.     push(v);
  44.     upd(l, min(tm, r), x, v * 2, tl, tm);
  45.     upd(max(tm + 1, l), r, x, v * 2 + 1, tm + 1, tr);
  46. }
  47.  
  48. ll sum(int l, int r, int v = 1, int tl = 0, int tr = n - 1)
  49. {
  50.     if (l > r)
  51.         return 0;
  52.     if (tree[v] != -1)
  53.     {
  54.         return 1LL * tree[v] * (r - l + 1);
  55.     }
  56.     if (tl == l && tr == r)
  57.     {
  58.         int tm = tl + tr >> 1;
  59.         return 0LL + sum(tl, tm, v * 2, tl, tm) + sum(tm + 1, tr, v * 2 + 1, tm + 1, tr);
  60.     }
  61.     int tm = tl + tr >> 1;
  62.     push(v);
  63.     return 0LL + sum(l, min(r, tm), v * 2, tl, tm) + sum(max(l, tm + 1), r, v * 2 + 1, tm + 1, tr);
  64. }
  65.  
  66. int main()
  67. {
  68.     //freopen("input.txt", "r", stdin);
  69.     //freopen("output.txt", "w", stdout);
  70.     ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
  71.  
  72.     cin >> n >> m;
  73.     tree.resize(4 * n, 0);
  74.     for (int i = 0; i < m; ++i)
  75.     {
  76.         char op;
  77.         cin >> op;
  78.         if (op == 'A')
  79.         {
  80.             int l, r, x;
  81.             cin >> l >> r >> x;
  82.             l--; r--;
  83.             upd(l, r, x);
  84.         }
  85.         else
  86.         {
  87.             int l, r;
  88.             cin >> l >> r;
  89.             l--; r--;
  90.             cout << sum(l, r) << endl;
  91.         }
  92.     }
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement