Advertisement
Guest User

Untitled

a guest
Nov 17th, 2021
163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.15 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int maxN = 2e5;
  6.  
  7. int n;
  8.  
  9. struct seg {
  10.     vector<long long> t = vector<long long> (maxN * 4);
  11.     vector<long long> lazy = vector<long long> (maxN * 4);
  12.     vector<long long> cur = vector<long long> (maxN * 4);
  13.     vector<bool> mark = vector<bool> (maxN * 4);
  14.  
  15.     void push(int x, long long range1, long long range2) {
  16.         if(mark[x]) {
  17.             mark[2 * x] = 1;
  18.             mark[2 * x + 1] = 1;
  19.             lazy[2 * x + 1] += lazy[x];
  20.             lazy[2 * x] += lazy[x];
  21.             t[2 * x] = cur[x] * range1 + lazy[x] * range1;
  22.             t[2 * x + 1] = cur[x] * range2 + lazy[x] * range2;
  23.             mark[x] = 0;
  24.             cur[2 * x] = cur[x];
  25.             cur[2 * x + 1] = cur[x];
  26.             lazy[x] = 0;
  27.         }
  28.         lazy[2 * x + 1] += lazy[x];
  29.         lazy[2 * x] += lazy[x];
  30.         t[2 * x] += lazy[x] * range1;
  31.         t[2 * x + 1] += lazy[x] * range2;
  32.         lazy[x] = 0;
  33.     }
  34.  
  35.     void assign(int x, int lx, int rx, int l, int r, long long v) {
  36.         if(lx >= l && rx <= r) {
  37.             t[x] = (rx - lx + 1) * v;
  38.             lazy[x] = 0;
  39.             mark[x] = 1;
  40.             cur[x] = v;
  41.             return;
  42.         }
  43.         if(lx > r || rx < l) {
  44.             return;
  45.         }
  46.         int m = (lx + rx) >> 1;
  47.         push(x, (m - lx + 1), (rx - m));
  48.         assign(2 * x, lx, m, l, r, v);
  49.         assign(2 * x + 1, m + 1, rx, l, r, v);
  50.         t[x] = t[2 * x + 1] + t[2 * x];
  51.     }
  52.  
  53.     void assign(int l, int r, long long v) {
  54.         assign(1, 0, n - 1, l, r, v);
  55.     }
  56.  
  57.     void add(int x, int lx, int rx, int l, int r, long long v) {
  58.         if(lx >= l && rx <= r) {
  59.             t[x] += (rx - lx + 1) * v;
  60.             lazy[x] += v;
  61.             return;
  62.         }
  63.         if(lx > r || rx < l) {
  64.             return;
  65.         }
  66.         int m = (lx + rx) >> 1;
  67.         push(x, (m - lx + 1), (rx - m));
  68.         add(2 * x, lx, m, l, r, v);
  69.         add(2 * x + 1, m + 1, rx, l, r, v);
  70.         t[x] = t[2 * x + 1] + t[2 * x];
  71.     }
  72.  
  73.     void add(int l, int r, long long v) {
  74.         add(1, 0, n - 1, l, r, v);
  75.     }
  76.  
  77.     long long query(int x, int lx, int rx, int l, int r) {
  78.         if(lx >= l && rx <= r) {
  79.             return t[x];
  80.         }
  81.         if(lx > r || rx < l) {
  82.             return 0;
  83.         }
  84.         int m = (lx + rx) >> 1;
  85.         push(x, (m - lx + 1), (rx - m));
  86.         return query(2 * x, lx, m, l, r) + query(2 * x + 1, m + 1, rx, l, r);
  87.     }
  88.     long long query(int l, int r) {
  89.         return query(1, 0, n - 1, l, r);
  90.     }
  91. };
  92.  
  93. int main() {
  94.     ios::sync_with_stdio(false);
  95.     cin.tie(nullptr);
  96.     int m;
  97.     cin >> n >> m;
  98.     seg st;
  99.     while(m--) {
  100.         int op;
  101.         cin >> op;
  102.         if(op == 1) {
  103.             int l, r; long long v;
  104.             cin >> l >> r >> v;
  105.             st.assign(l, r-1, v);
  106.         }
  107.         if(op == 2) {
  108.             int l, r; long long v;
  109.             cin >> l >> r >> v;
  110.             st.add(l, r - 1, v);
  111.         }
  112.         if(op == 3) {
  113.             int l, r;
  114.             cin >> l >> r;
  115.             cout << st.query(l, r - 1) << '\n';
  116.         }
  117.     }
  118.     return 0;
  119. }
  120.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement