peltorator

Дерево Отрезков С Массовым Обновлением

Feb 22nd, 2017
215
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define integer ll //change
  2.  
  3. const integer INF = 3e18; // change
  4. const int N = (1 << 20); // we need just 4n + 10
  5.  
  6. integer neutr = -INF, neutr2 = 0; //change(neutr and update neutr)
  7.  
  8. integer f(integer a, integer b) // operation
  9. {
  10.     return max(a, b); //change
  11. }
  12.  
  13. void g(integer &a, integer b) // update operation
  14. {
  15.     if (a == neutr2)
  16.         a = b;
  17.     else
  18.         a += b; //change
  19. }
  20.  
  21. struct Tree
  22. {
  23.     integer t[N], psh[N], n;
  24.     vector<integer> vec;
  25.  
  26.     Tree(int n):
  27.         n(n) {}
  28.  
  29.     void build(int v, int l, int r)
  30.     {
  31.         if (l + 1 == r)
  32.         {
  33.             t[v] = vec[l];
  34.             return;
  35.         }
  36.         int mid = ((r + l) >> 1);
  37.         build((v << 1), l, mid);
  38.         build(((v << 1) | 1), mid, r);
  39.         t[v] = f(t[(v << 1)], t[((v << 1) | 1)]);
  40.     }
  41.  
  42.     Tree(vector<integer> v)
  43.     {
  44.         vec = v;
  45.         n = vec.size();
  46.         build(1, 0, n);
  47.     }
  48.  
  49.     void push(int v)
  50.     {
  51.         if (psh[v] != neutr2)
  52.         {
  53.             g(psh[(v << 1)], psh[v]);
  54.             g(psh[((v << 1) | 1)], psh[v]);
  55.             psh[v] = neutr2;
  56.         }
  57.     }
  58.  
  59.     void upd(int v, int l, int r, int ql, int qr, integer val)
  60.     {
  61.         if (ql >= r || l >= qr)
  62.             return;
  63.         push(v);
  64.         if (ql <= l && r <= qr)
  65.         {
  66.             g(t[v], val);
  67.             g(psh[v], val);
  68.             return;
  69.         }
  70.         int mid = ((r + l) >> 1);
  71.         upd((v << 1), l, mid, ql, qr, val);
  72.         upd(((v << 1) | 1), mid, r, ql, qr, val);
  73.         t[v] = f(t[(v << 1)], t[((v << 1) | 1)]);
  74.     }
  75.  
  76.     void upd(int l, int r, integer val)
  77.     {
  78.         upd(1, 0, n, l, r, val);
  79.     }
  80.  
  81.     integer find(int v, int l, int r, int ql, int qr)
  82.     {
  83.         if (ql >= r || l >= qr)
  84.             return neutr;
  85.         push(v);
  86.         if (ql <= l && r <= qr)
  87.             return t[v];
  88.         int mid = ((r + l) >> 1);
  89.         return f(find((v << 1), l, mid, ql, qr), find(((v << 1) | 1), mid, r, ql, qr));
  90.     }
  91.  
  92.     integer find(int l, int r)
  93.     {
  94.         return find(1, 0, n, l, r);
  95.     }
  96. };
RAW Paste Data