Advertisement
MaxObznyi

D

Jun 25th, 2022
792
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #define int long long
  3. using namespace std;
  4.  
  5. const int N = 2e5 + 5;
  6.  
  7. struct node {
  8.     int sum, p;
  9. };
  10.  
  11. int n, q, a[N];
  12. node t[4*N];
  13.  
  14. void build(int v, int vl, int vr) {
  15.     if (vl == vr) {
  16.         t[v].sum = a[vl];
  17.         t[v].p = a[vl];
  18.         return;
  19.     }
  20.     int vm = (vl + vr) / 2;
  21.     build(2 * v, vl, vm);
  22.     build(2 * v + 1, vm + 1, vr);
  23.  
  24.     t[v].sum = t[2 * v].sum + t[2 * v + 1].sum;
  25.     t[v].p = 0;///no promise
  26. }
  27.  
  28. void push(int v, int vl, int vr) {
  29.     if (t[v].p == 0)
  30.         return;
  31.     int vm = (vl + vr) / 2;
  32.  
  33.     t[2 * v].p = t[v].p;
  34.     t[2 * v + 1].p = t[v].p;
  35.  
  36.     t[2 * v].sum = (vm - vl + 1) * t[v].p;
  37.     t[2 * v + 1].sum = (vr - vm) * t[v].p;
  38.  
  39.     t[v].p = 0;
  40. }
  41.  
  42. void update(int v, int vl, int vr, int l, int r, int x) {
  43.     //cout << v << ' ' << vl << ' ' << vr << ' ' << l << ' ' << r << endl;
  44.     if (vl == l && vr == r) {
  45.         t[v].p = x;
  46.         t[v].sum = x * (r - l + 1);
  47.         return;
  48.     }
  49.     int vm = (vl + vr) / 2;
  50.     push(v, vl, vr);
  51.     if (r <= vm)
  52.         update(2 * v, vl, vm, l, r, x);
  53.     else if (l > vm)
  54.         update(2 * v + 1, vm + 1, vr, l, r, x);
  55.     else {
  56.         update(2 * v, vl, vm, l, vm, x);
  57.         update(2 * v + 1, vm + 1, vr, vm + 1, r, x);
  58.     }
  59.     t[v].sum = t[2 * v].sum + t[2 * v + 1].sum;
  60. }
  61.  
  62. int get(int v, int vl, int vr, int l, int r) {
  63.     if (vl == l && vr == r)
  64.         return t[v].sum;
  65.     int vm = (vl + vr) / 2;
  66.     push(v, vl, vr);
  67.     if (r <= vm)
  68.         return get(2 * v, vl, vm, l, r);
  69.     else if (l > vm)
  70.         return get(2 * v + 1, vm + 1, vr, l, r);
  71.     else {
  72.         return get(2 * v, vl, vm, l, vm) + get(2 * v + 1, vm + 1, vr, vm + 1, r);
  73.     }
  74.  
  75. }
  76.  
  77. signed main()
  78. {
  79.     cin >> n >> q;
  80.     for (int i = 1; i <= n; i++)
  81.         cin >> a[i];
  82.     build(1, 1, n);
  83.     while (q--) {
  84.         int t;
  85.         cin >> t;
  86.         if (t == 1) {
  87.             int l, r, x;
  88.             cin >> l >> r >> x;
  89.             update(1, 1, n, l, r, x);
  90.         } else {
  91.             int l, r;
  92.             cin >> l >> r;
  93.             cout << get(1, 1, n, l, r) << "\n";
  94.         }
  95.     }
  96.     return 0;
  97. }
  98.  
Advertisement
RAW Paste Data Copied
Advertisement