E-olymp 2310

Ссылка на задачу

• E-olymp #2310 — И снова сумма...

Решение

#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);
        }
    }
}