Salvens

Untitled

Jul 24th, 2023
791
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 KB | None | 0 0
  1. #include <array>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. #define int long long
  7.  
  8. const int INF = 1e18 + 7;
  9. const int MAXN = 1e5;
  10.  
  11. array<int, 4 * MAXN> tree;
  12. array<int, 4 * MAXN> upd;
  13.  
  14. void push(int x, int lx, int rx) {
  15.     if (upd[x] == INF) {
  16.         return;
  17.     }
  18.     if (lx + 1 != rx) {
  19.         upd[2 * x + 1] = upd[x];
  20.         upd[2 * x + 2] = upd[x];
  21.     }
  22.     tree[x] = upd[x] * (rx - lx);
  23.     upd[x] = INF;
  24. }
  25.  
  26. void update(int x, int lx, int rx, int l, int r, int v) {
  27.     push(x, lx, rx);
  28.     if (rx <= l || lx >= r) {
  29.         return;
  30.     }
  31.     if (lx >= l && rx <= r) {
  32.         upd[x] = v;
  33.         push(x, lx, rx);
  34.         return;
  35.     }
  36.     int mid = (lx + rx) / 2;
  37.     update(x * 2 + 1, lx, mid, l, r, v);
  38.     update(x * 2 + 2, mid, rx, l, r, v);
  39.     tree[x] = tree[x * 2 + 1] + tree[x * 2 + 2];
  40. }
  41.  
  42. int sum(int x, int lx, int rx, int l, int r) {
  43.     push(x, lx, rx);
  44.     if (rx <= l || lx >= r) {
  45.         return 0;
  46.     }
  47.     if (lx >= l && rx <= r) {
  48.         return tree[x];
  49.     }
  50.     int mid = (lx + rx) / 2;
  51.     return sum(x * 2 + 1, lx, mid, l, r) + sum(x * 2 + 2, mid, rx, l, r);
  52. }
  53.  
  54. signed main() {
  55.     ios_base::sync_with_stdio(false);
  56.     cin.tie(nullptr);
  57.     int n, m;
  58.     cin >> n >> m;
  59.     fill(upd.begin(), upd.end(), INF);
  60.     for (int i = 0; i < m; ++i) {
  61.         int t, l, r;
  62.         cin >> t >> l >> r;
  63.         if (t == 1) {
  64.             int v;
  65.             cin >> v;
  66.             update(0, 0, n, l, r, v);
  67.         } else {
  68.             cout << sum(0, 0, n, l, r) << '\n';
  69.         }
  70.     }
  71. }
Advertisement
Add Comment
Please, Sign In to add comment