MickyOr

Untitled

Nov 29th, 2016
110
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct node
  6. {
  7.     int maximo, minimo;
  8.     int sum, mul;
  9.  
  10.     void join(node l, node r)
  11.     {
  12.         maximo = max(l.maximo, r.maximo);
  13.         minimo = min(l.minimo, r.minimo);
  14.         sum = l.sum + r.sum;
  15.         mul = l.mul * r.mul;
  16.     }
  17. };
  18.  
  19. node T[4 * 100000];
  20. int A[100000];
  21.  
  22. void init(int b, int e, int nodo)
  23. {
  24.     int mid = (b+e)/2, L = 2 * nodo + 1, R = L + 1;
  25.     if (b == e) T[nodo].maximo = T[nodo].minimo = T[nodo].sum = T[nodo].mul = A[b]; // o como quieras inicializar el nodo, podrias hacer una funcion
  26.     else
  27.     {
  28.         init(b, mid, L);
  29.         init(mid+1, e, R);
  30.         T[nodo].join(T[L], T[R]);
  31.     }
  32. }
  33.  
  34. void update(int b, int e, int nodo, int pos, int val)
  35. {
  36.     int mid = (b+e)/2, L = 2 * nodo + 1, R = L + 1;
  37.     if (b == e) T[nodo].maximo = T[nodo].minimo = T[nodo].sum = T[nodo].mul = val;
  38.     else
  39.     {
  40.         if (pos <= mid) update(b, mid, L, pos, val);
  41.         else update(mid+1, e, R, pos, val);
  42.         T[nodo].join(T[L], T[R]);
  43.     }
  44. }
RAW Paste Data