Advertisement
Guest User

Untitled

a guest
Mar 19th, 2014
702
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.03 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <map>
  6. #include <set>
  7.  
  8. using namespace std;
  9.  
  10. class Treap {
  11.  
  12. private:
  13.  
  14. struct node {
  15.     node *left, *right;
  16.     int x, y;
  17.     int cost, size;
  18.     long long add, sum;
  19.     node () {left = right = NULL; cost = sum = add = 0ll, size = 0;}
  20.     node (int X, int Y, int COST) {left = right = NULL; x = X, y = Y, cost = COST, sum = 0ll, size = 1, add = 0ll; }
  21. };
  22.  
  23. node *treap;
  24.  
  25. void split (node* T, node*& L, node*& R, int x);
  26. void merge (node* L, node* R, node *& T);
  27. void recalc (node*& T);
  28. long long sumOf (node* T) {return T ? T->sum : 0ll;};
  29. int sizeOf (node* T) {return T ? T->size : 0; }
  30. void push (node*& T);
  31.  
  32. public:
  33. Treap () {treap = NULL; }
  34. void add (int cost);
  35. long long get (int l, int r);
  36. void update (int l, int r, int dx);
  37. int size () {return sizeOf(treap); }
  38. int sum () {return sumOf (treap); }
  39.  
  40. };                                                                     
  41.  
  42. void Treap :: recalc (node*& T) {
  43.     if (T) {
  44.         T->size = sizeOf (T->left) + sizeOf (T->right) + 1;
  45.         T->sum = sumOf (T->left) + sumOf (T->right) + T->cost;
  46.     }  
  47. }
  48.  
  49. void Treap :: push (node*& T) {
  50.     if (T) {
  51.         if (T->right)
  52.             T->right->add += T->add;
  53.         if (T->left)
  54.             T->left->add += T->add;
  55.         T->sum += T->add * T->size;
  56.         T->add = 0ll;
  57.     }  
  58. }
  59.  
  60. void Treap :: split (node* T, node*& L, node*& R, int x) {
  61.     if (!T) {
  62.         L = R = NULL;
  63.         return;
  64.     }
  65.     push (T);
  66.     if (T->x < x) {
  67.         L = T;
  68.         split (T->right, L->right, R, x);
  69.         recalc (L);
  70.     } else {
  71.         R = T;
  72.         split (T->left, L, R->left, x);
  73.         recalc (R);
  74.     }
  75. }
  76.  
  77. void Treap :: merge (node* L, node* R, node*& T) {
  78.     push (L);
  79.     push (R);
  80.     if (!L || !R) {
  81.         T = L ? L : R;
  82.         return;
  83.     }
  84.     if (L->y > R->y) {
  85.         T = L;
  86.         merge (L->right, R, T->right);
  87.     } else {
  88.         T = R;
  89.         merge (L, R->left, T->left);
  90.     }
  91.     recalc (T);    
  92. }
  93.  
  94. void Treap :: add (int cost) {
  95.     if (!treap) {
  96.         treap = new node (1, rand(), cost);
  97.         return;
  98.     }
  99.     int x = sizeOf(treap) + 1;
  100.     node *M = new node (x, rand(), cost);
  101.     node *L, *R;
  102.     split (treap, L, R, x);
  103.     merge (L, M, L);
  104.     merge (L, R, treap);
  105. }
  106.  
  107. long long Treap :: get (int l, int r) {
  108.     node *L = 0, *R = 0, *M = 0, *N = 0;              
  109.     split (treap, L, R, l);                                  
  110.     split (R, N, M, r + 1);
  111.     long long res = sumOf (N);
  112.     merge (N, M, R);
  113.     merge (L, R, treap);                              
  114.     return res;
  115. }
  116.  
  117. void Treap :: update (int l, int r, int dx) {
  118.     node *L = 0, *R = 0, *M = 0, *N = 0;
  119.     split (treap, L, R, l);
  120.     split (R, N, M, r + 1);
  121.     N->add += dx;
  122.     merge (N, M, R);
  123.     merge (L, R, treap);   
  124. }
  125.  
  126. Treap myTreap;
  127.  
  128. int main () {
  129.  
  130.     srand (time (0));
  131.     int n;
  132.     cin >> n;
  133.     for (int i = 0; i < n; i++) {
  134.         int c;
  135.         cin >> c;
  136.         myTreap.add (c);
  137.     }
  138.  
  139.     int m;
  140.     cin >> m;
  141.     while (m--) {
  142.         int l, r, x;
  143.         char ch;
  144.         cin >> ch >> l >> r;                                                    
  145.         if (ch == 'g')
  146.             cout << myTreap.get (l, r) << "\n";
  147.         else {
  148.             cin >> x;
  149.             myTreap.update(l, r, x);
  150.         }
  151.     }
  152.    
  153.     return 0;
  154. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement