Просмотр кода страницы E-olymp 2310

== Ссылка на задачу ==
* [http://www.e-olymp.com/ru/problems/2310 E-olymp #2310 &mdash; И снова сумма...]

== Решение ==
 #include <stdio.h>
 #include <stdlib.h>
 
 class Treap {
 
     struct TreapNode {
         int key, priority;
         long long keysSum;
         TreapNode *left, *right;
         TreapNode(int key) : key(key), keysSum(key), priority(rand()), left(0), right(0) {}
     } *root;
 
     long long getKeysSum(TreapNode *node) {
         return node ? node->keysSum : 0;
     }
 
     void update(TreapNode *node) {
         if (!node)
             return;
         node->keysSum = node->key + getKeysSum(node->left) + getKeysSum(node->right);
     }
 
     TreapNode *merge(TreapNode *a, TreapNode *b) {
         if (!a || !b)
             return a ? a : b;
         if (a->priority > b->priority) {
             a->right = merge(a->right, b);
             update(a);
             return a;
         } else {
             b->left = merge(a, b->left);
             update(b);
             return b;
         }
     }
 
     void split(TreapNode *t, int splitKey, TreapNode *&a, TreapNode *&b) {
         if (!t) {
             a = b = 0;
             return;
         }
         if (t->key < splitKey) {
             split(t->right, splitKey, t->right, b);
             a = t;
         } else {
             split(t->left, splitKey, a, t->left);
             b = t;
         }
         update(a);
         update(b);
     }
 
 public:
 
     Treap() : root(0) {}
 
     void insertUnique(int key) {
         TreapNode *tLess, *tEqual, *tGreater;
         split(root, key, tLess, tGreater);
         split(tGreater, key + 1, tEqual, tGreater);
         if (!tEqual)
             tEqual = new TreapNode(key);
         root = merge(tLess, merge(tEqual, tGreater));
     }
 
     long long keysSum(int keyL, int keyR) {
         TreapNode *tLess, *tIn, *tGreater;
         split(root, keyL, tLess, tGreater);
         split(tGreater, keyR + 1, tIn, tGreater);
         long long result = getKeysSum(tIn);
         root = merge(tLess, merge(tIn, tGreater));
         return result;
     }
 
 } treap;
 
 int main() {
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
 
     int queriesCount;
     scanf("%d", &queriesCount);
     long long previousResult = 0;
     for (int i = 0; i < queriesCount; i++) {
         char queryType;
         scanf(" %c", &queryType);
         if (queryType == '+') {
             int key;
             scanf("%d", &key);
             treap.insertUnique((key + previousResult) % (int)1e9);
             previousResult = 0;
         } else {
             int keyL, keyR;
             scanf("%d%d", &keyL, &keyR);
             previousResult = treap.keysSum(keyL, keyR);
             printf("%lld\n", previousResult);
         }
     }
 }



[[Category: Сборник задач: E-olymp]]
[[Category: Задачи: Декартово дерево]]