Ctrlalt: Новая страница: «== Ссылка на задачу == * [http://www.e-olymp.com/ru/problems/2310 E-olymp #2310 — И снова сумма...] == Решение == #include…»

2016-04-24T21:41:03Z

Новая страница: «== Ссылка на задачу == * [http://www.e-olymp.com/ru/problems/2310 E-olymp #2310 — И снова сумма...] == Решение == #include…»

Новая страница

== Ссылка на задачу ==
* [http://www.e-olymp.com/ru/problems/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);
}
}
}

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

E-olymp 2310 - История изменений

Ctrlalt: Новая страница: «== Ссылка на задачу == * [http://www.e-olymp.com/ru/problems/2310 E-olymp #2310 — И снова сумма...] == Решение == #include…»