Advertisement
Guest User

Untitled

a guest
Jan 18th, 2020
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.65 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 1e5 + 100;
  6.  
  7. long long t[MAXN * 4], f[MAXN * 4];
  8.  
  9. void push(int v, int d)
  10. {
  11.     if(f[v] != -1)
  12.     {
  13.         t[v] = d * f[v];
  14.         f[v * 2] = f[v * 2 + 1] = f[v];
  15.         f[v] = -1;
  16.     }
  17. }
  18.  
  19. void update(int v, int l, int r, int ql, int qr, int val)
  20. {
  21.     push(v, r - l + 1);
  22.     if(ql > qr)
  23.         return;
  24.     if(l == ql and r == qr)
  25.     {
  26.         f[v] = val;
  27.         push(v, r - l + 1);
  28.     }
  29.     else
  30.     {
  31.         int m = (l + r) / 2;
  32.         update(v * 2, l, m, ql, min(qr, m), val);
  33.         update(v * 2 + 1, m + 1, r, max(m + 1, ql), qr, val);
  34.  
  35.         t[v] = t[v * 2] + t[v * 2 + 1];
  36.     }
  37. }
  38.  
  39. long long sum(int v, int l, int r, int ql, int qr)
  40. {
  41.     if(ql > qr)
  42.         return 0;
  43.     push(v, r - l + 1);
  44.     if(ql == l and qr == r)
  45.         return t[v];
  46.  
  47.     int m = (l + r) / 2;
  48.     return sum(v * 2, l, m, ql, min(m, qr)) + sum(v * 2 + 1, m + 1, r, max(m + 1, ql), qr);
  49. }
  50.  
  51. int main()
  52. {
  53.     //ускорение ввода
  54.     ios::sync_with_stdio(0);
  55.     cin.tie(0);
  56.     cout.tie(0);
  57.  
  58.     //Ввод-вывод из файла
  59.     freopen("sum.in", "r", stdin);
  60.     freopen("sum.out", "w", stdout);
  61.  
  62.     //инициализачия флагов
  63.     fill(f, f + 4 * MAXN, -1);
  64.  
  65.     //ввод
  66.     int n, k;
  67.     cin >> n >> k;
  68.     while(k--)
  69.     {
  70.         char t;
  71.         int l, r;
  72.         cin >> t >> l >> r;
  73.         l--, r--;
  74.         if(t == 'A')
  75.         {
  76.             int x;
  77.             cin >> x;
  78.             update(1, 0, n - 1, l, r, x);
  79.         }
  80.         else
  81.             cout << sum(1, 0, n - 1, l, r) << '\n';
  82.     }
  83.     return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement