Bekzhan

Untitled

Mar 7th, 2013
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. struct node
  8. {
  9.     long long sum;
  10.     int flag;
  11.  
  12.     node() : sum(0), flag(-1) {}
  13. }t[600000];
  14.  
  15. void push(int v, int l, int r)
  16. {
  17.     if (t[v].flag != -1 && l <= r)
  18.         {
  19.             t[v << 1].flag = t[(v << 1) + 1].flag = t[v].flag;
  20.  
  21.             t[v].sum = (r - l + 1) * 1ll * t[v].flag;
  22.  
  23.             t[v].flag = -1;
  24.         }
  25. }
  26.  
  27. void upd(int v, int l, int r, int zl, int zr, int val)
  28. {
  29.     if (l > r || r < zl || l > zr)
  30.         return;
  31.  
  32.     push(v, l, r);
  33.  
  34.     int m = (l + r) >> 1;
  35.  
  36.     if (l >= zl && r <= zr)
  37.         {  
  38.             t[v].flag = val;
  39.             push(v, l, r);
  40.             push(v << 1, l, m);
  41.             push((v << 1) + 1, m + 1, r);
  42.             return;
  43.         }
  44.  
  45.     upd((v << 1),     l,     m, zl, zr, val);
  46.     upd((v << 1) + 1, m + 1, r, zl, zr, val);
  47.  
  48.     push(v << 1, l, m);
  49.     push((v << 1) + 1, m + 1, r);
  50.  
  51.     t[v].sum = t[v << 1].sum + t[(v << 1) + 1].sum;
  52. }
  53.  
  54. long long sum(int v, int l, int r, int zl, int zr)
  55. {
  56.     if (l > r || l > zr || r < zl)
  57.         return 0 ;
  58.  
  59.     int m = (l + r) >> 1;
  60.  
  61.     push(v, l, r);
  62.     push(v << 1, l, m);
  63.     push((v << 1) + 1, m + 1, r);
  64.  
  65.     if (l >= zl && r <= zr)
  66.         return t[v].sum;
  67.  
  68.     return (sum(v << 1, l, m, zl, zr) + sum((v << 1) + 1, m + 1, r, zl, zr));
  69. }
  70.  
  71. int main()
  72. {
  73.     freopen("sum.in", "r", stdin);
  74.     freopen("sum.out", "w", stdout);
  75.    
  76.     ios_base :: sync_with_stdio(false);
  77.  
  78.     int n, k;
  79.  
  80.     cin >> n >> k;
  81.  
  82.     char c;
  83.  
  84.     int l, r, val;
  85.  
  86.     while (k--)
  87.         {
  88.             cin >> c >> l >> r;
  89.  
  90.             l--, r--;
  91.  
  92.             if (c == 'A')
  93.                 {
  94.                     cin >> val;
  95.                     upd(1, 0, n - 1, l, r, val);
  96.                 }
  97.             else
  98.                 cout << sum(1, 0, n - 1, l, r) << endl;
  99.         }
  100.  
  101.     return 0;
  102.  
  103.    
  104. }
Advertisement
Add Comment
Please, Sign In to add comment