Advertisement
Guest User

Untitled

a guest
Jul 4th, 2015
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.96 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<stack>
  4. #include<queue>
  5. #include<set>
  6. #include<iomanip>
  7. #include<complex>
  8. #include<vector>
  9. #include<map>
  10. #include<algorithm>
  11. #include<cmath>
  12. #include<string>
  13. #include<bitset>
  14. #include<memory.h>
  15. #include<cassert>
  16. #include<ctime>
  17.  
  18.  
  19. using namespace std;
  20.  
  21. #pragma comment(linker, "/STACK:36777216")
  22.  
  23. #define For(i,l,r) for (int i = l; i < r + 1; i ++)
  24. #define ForI(it , s , T) for (T :: iterator it = s.begin(); it != s.end() ; ++ it )
  25. #define LL long long
  26. #define iinf 1000000000
  27. #define linf 4000000000000000000LL
  28. #define MOD  (1000000007)
  29. #define Pi 3.1415926535897932384
  30. #define bit(mask,i) ((mask>>i)&1)
  31. #define pb(x) push_back(x)
  32. #define mk(x,y) make_pair(x,y)
  33. #define sqr(x) ((x)*(x))
  34. #define pause cin.get();cin.get();
  35. #define fir first
  36. #define sec second
  37. #define ln(x) log(x)
  38. #define pii pair<int,int>
  39. #define y1 y23423423
  40.  
  41. const int Nmax = 100100;
  42. const int Direction[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
  43.  
  44. struct Segm {
  45.        int l, r;
  46.        int color;
  47.        bool isColored;
  48.        LL sum;
  49.        Segm(){};
  50. } tree[4*Nmax];
  51.  
  52. void build(int v,int l,int r) {
  53.      tree[v].l = l, tree[v].r = r;
  54.      tree[v].isColored = false;
  55.      tree[v].color = tree[v].sum = 0;
  56.      if (l == r) return ;
  57.      int mid = (l + r) >> 1;
  58.  
  59.      build(v + v, l, mid);
  60.      build(v + v + 1, mid + 1, r);    
  61. }
  62.  
  63. inline void push(int v) {
  64.        if (!tree[v].isColored) return ;
  65.        tree[v].sum += (tree[v].r - tree[v].l + 1) * 1ll * tree[v].color;
  66.        tree[v].isColored = false;
  67.        int x = tree[v].color;
  68.        tree[v].color = 0;
  69.        
  70.        if (tree[v].l == tree[v].r) return ;
  71.        tree[v + v].color += x;
  72.        tree[v + v + 1].color += x;
  73.        tree[v + v].isColored = tree[v + v + 1].isColored = true;
  74. }
  75.  
  76. void update(int v,int l,int r,int x) {
  77.      push(v);
  78.      if (tree[v].l == l && tree[v].r == r) {
  79.         tree[v].isColored = true;
  80.         tree[v].color = x;
  81.         return ;
  82.      }
  83.      int mid = (tree[v].l + tree[v].r) >> 1;
  84.      if (l <= mid)
  85.         update(v + v, l, min(mid, r), x);
  86.      if (r > mid)
  87.         update(v + v + 1, max(mid + 1, l), r, x);
  88.      push(v + v), push(v + v + 1);
  89.      tree[v].sum = (tree[v + v].sum + tree[v + v + 1].sum);
  90. }
  91.  
  92. LL getSum(int v,int l,int r) {
  93.    if (l > r) return 0;
  94.    push(v);
  95.    if (tree[v].l == l && tree[v].r == r) {
  96.       return tree[v].sum;
  97.    }
  98.    int mid = (tree[v].l + tree[v].r) >> 1;
  99.    return getSum(v + v, l, min(r,mid)) + getSum(v + v + 1, max(l, mid + 1), r);
  100. }
  101.  
  102. int main() {
  103.     ios_base::sync_with_stdio(0);
  104.     int n,q;
  105.     cin >> n >> q;
  106.     build(1,1,n);
  107.     while (q --> 0) {
  108.           int ch;
  109.           cin >> ch;
  110.           if (ch == 0) {
  111.              int l,r,x;
  112.              cin >> l >> r >> x;
  113.              update(1,l,r,x);
  114.           }
  115.           else {
  116.                int l,r;
  117.                cin >> l >> r;
  118.                cout << getSum(1,l,r) << endl;
  119.           }
  120.     }
  121.     return 0;
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement