Advertisement
Guest User

Untitled

a guest
Mar 19th, 2018
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4.  
  5. using namespace std;
  6.  
  7. struct rt
  8. {
  9.   ll sum;
  10.   ll x;
  11. };
  12.  
  13. rt tree[400001];
  14.  
  15. void push(int v, int tl, int tr)
  16. {
  17.     if(tree[v].x == -1)
  18.       return;
  19.     tree[2*v].x = tree[v].x;
  20.     tree[2*v+1].x = tree[v].x;
  21.     int mid = (tl+tr)/2;
  22.     tree[2*v].sum = 1LL*(mid-tl+1)*tree[v].x;
  23.     tree[2*v+1].sum = 1LL*(tr-mid)*tree[v].x;
  24.     tree[v].x = -1;
  25. }
  26.  
  27. void build(int v, int l, int r)
  28. {
  29.   if (r > l)
  30.     return;
  31.   tree[v].sum = 0;
  32.   tree[v].x = -1;
  33.   if (l == r)
  34.     return;
  35.   int mid = (l+r)/2;
  36.   int new_v = 2*v;
  37.   build(new_v, l, mid);
  38.   build(new_v+1, mid+1, r);
  39. }
  40.  
  41. void Update(int v, int tl, int tr, int l, int r, int x)
  42. {
  43.     if (l>r)
  44.       return;
  45.      if (l == tl && r == tr)
  46.      {
  47.        tree[v].x = x;
  48.        tree[v].sum = 1LL*x*(r-l+1);
  49.         return;
  50.     }
  51.     push(v, tl, tr);
  52.     int mid = (tl+tr)/2;
  53.     Update(2*v,tl, mid, l, min(r, mid), x);
  54.     Update(2*v+1, mid+1, tr, max(l, mid+1), r, x);
  55.     tree[v].sum = tree[2*v].sum+tree[2*v+1].sum;
  56. }
  57.  
  58.  
  59. ll sum(int v, int tl, int tr, int l, int r)
  60. {
  61.   if(l > r)
  62.     return 0;
  63.   if (l == tl && r == tr)
  64.     return tree[v].sum;
  65.   push(v, tl, tr);
  66.   int mid = (tl+tr)/2;
  67.   return sum(2*v, tl, mid, l ,min(mid, r))+ sum(2*v+1, mid+1, tr, max(mid+1, l), r);
  68.  
  69. }
  70. int main()
  71. {
  72.     ifstream cin("sum.in");
  73.     int n, q;
  74.     cin >> n >> q;
  75.     build(1, 1, n);
  76.     for (int i = 0; i < q; i++)
  77.     {
  78.       char tp;
  79.       int l , r;
  80.       cin >> tp >> l >> r;
  81.       if(tp == 'A')
  82.       {
  83.         int x;
  84.         cin >> x;
  85.         Update(1, 1, n, l, r, x);
  86.         continue;
  87.       }
  88.       cout << sum(1, 1, n, l, r) << endl;
  89.     }
  90.  
  91.     return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement