Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <math.h>
- #include <random>
- using namespace std;
- struct Node {
- long long x, y;
- long long sum = 0;
- Node *left, *right;
- }; //+
- Node * root = nullptr;
- long long n, x, y;
- char c;
- long long result = 0;
- long long a[20000000];
- //написать все связанное с суммой
- void rangeCalc(Node *node) {
- if (node == nullptr)
- return;
- long long w = node->right == nullptr ? 0 : node->right->sum;
- w += node->left == nullptr ? 0 : node->left->sum;
- node->sum = w + node->x;
- } //+
- bool contains(Node *node, long long e) {
- if (node == nullptr)
- return false;
- if (e == node->x)
- return true;
- if (e > node->x) {
- return contains(node->right, e);
- }
- else {
- return contains(node->left, e);
- }
- //to->y = node->y;
- } //+
- Node * next(Node *node, long long e) {
- Node * current = node, *successor = nullptr;
- while (current != nullptr) {
- if (current->x > e) {
- successor = current;
- current = current->left;
- } else
- current = current->right;
- }
- if (successor == nullptr) {
- Node *to = new Node();
- to->x = INT64_MIN;
- return to;
- }
- return successor;
- }
- Node * prev(Node *node, long long e) {
- Node * current = node, *predecessor = nullptr;
- while (current != nullptr) {
- if (current->x < e) {
- predecessor = current;
- current = current->right;
- } else
- current = current->left;
- }
- if (predecessor == nullptr) {
- Node *to = new Node();
- to->x = INT64_MAX;
- return to;
- }
- return predecessor;
- } //+
- Node * merge(Node *A, Node* B) {
- if (A == nullptr) {
- rangeCalc(A);
- rangeCalc(B);
- return B;
- } //+
- if (B == nullptr) {
- rangeCalc(A);
- rangeCalc(B);
- return A;
- } //+
- if (A->y < B->y) {
- A->right = merge(A->right, B);
- rangeCalc(B);
- rangeCalc(A);
- return A;
- } //+
- else {
- B->left = merge(A, B->left);
- rangeCalc(A);
- rangeCalc(B);
- return B;
- } //+
- }
- pair<Node *, Node *> split(Node *A, long long e) {
- if (A == nullptr) {
- return make_pair(nullptr, nullptr);
- }
- /*if (A->x == x) {
- Node * res1 = merge(A, A->right);
- rangeCalc(res1);
- pair<Node *, Node *> res = make_pair(A->left, res1);
- rangeCalc(A);
- return make_pair(res.first, res.second);
- }*/
- /*if (A->x == e) {
- Node * res1 = merge(A->left, A);
- rangeCalc(res1);
- pair<Node *, Node *> res = make_pair(res1, A->right);
- rangeCalc(A);
- return make_pair(res.first, res.second);
- }*/
- if (A->x < e) {
- pair<Node *, Node *> res = split(A->right, e);
- //rangeCalc(res.second);
- A->right = res.first;
- rangeCalc(A);
- rangeCalc(res.first);
- return make_pair(A, res.second);
- }
- else {
- pair<Node *, Node *> res = split(A->left, e);
- //rangeCalc(res.first);
- A->left = res.second;
- rangeCalc(A);
- rangeCalc(res.second);
- return make_pair(res.first, A);
- }
- }
- Node * insert(Node * A, Node * nd) {
- rangeCalc(A);
- pair<Node *, Node *> res = split(A, nd->x + 1);
- rangeCalc(res.first);
- rangeCalc(res.second);
- Node * T = merge(res.first, nd);
- rangeCalc(T);
- rangeCalc(res.second);
- A = merge(T, res.second);
- rangeCalc(A);
- return A;
- }
- /*pair<Node *, long long> sum(Node *node, long long l, long long r) { //[l, r)
- long long leftSum = 0;
- long long rightSum = 0;
- long long nodeRes = 0;
- if (node == nullptr) {
- return make_pair(node, 0);
- }
- if (node->x >= l && node->x < r) { //+
- nodeRes = node->x;
- }
- if (node->leftBound >= r || node->rightBound <= l) { //+
- rangeCalc(node);
- return make_pair(node, 0);
- }
- if (node->leftBound >= l && node->rightBound <= r) {
- rangeCalc(node);
- long long w = node->right == nullptr ? 0 : node->right->sum;
- w += node->left == nullptr ? 0 : node->left->sum;
- node->sum = w + node->x;
- return make_pair(node, w + node->x);
- }
- if (node->left != nullptr) {
- //pair<Node *, long long> resu = sum(node->left, max(l, node->leftBound), min(node->x, r));
- pair<Node *, long long> resu = sum(node->left, max(l, node->left->leftBound), min(node->left->rightBound, r));
- node->left = resu.first;
- rangeCalc(node->left);
- leftSum = resu.second;
- }
- if (node->right != nullptr) {
- //pair<Node *, long long> resu = sum(node->right, max(l, node->x), min(r, node->rightBound));
- pair<Node *, long long> resu = sum(node->right, max(l, node->right->leftBound), min(node->right->rightBound, r));
- node->right = resu.first;
- rangeCalc(node->right);
- rightSum = resu.second;
- }
- rangeCalc(node);
- return make_pair(node, leftSum + rightSum + nodeRes);
- }*/
- pair<Node *, long long> sum(Node *node, long long l, long long r) {
- //TreapNode *t1, *t2, *t3;
- pair<Node *, Node *> res = split(node, l);
- rangeCalc(res.first);
- rangeCalc(res.second);
- pair<Node *, Node *> res1 = split(res.second, r + 1);
- rangeCalc(res1.first);
- rangeCalc(res1.second);
- long long ans = res1.first == nullptr ? 0 : res1.first->sum;
- Node * back = merge(res1.first, res1.second);
- rangeCalc(back);
- node = merge(res.first, back);
- rangeCalc(node);
- return make_pair(node, ans);
- }
- int main() {
- cin >> n;
- long long E = 1e9;
- random_device rd;
- mt19937 mersenne(rd());
- result = 0;
- for (int i = 0; i < n; i++) { //+
- cin >> c;
- cin >> x;
- //if (c == '+' && next(root, (x + result - 1))->x != ((x + result) % 1000000000)) {
- if (c == '+' && !contains(root, (x + result + E) % E)) {
- //
- Node *to = new Node();
- to->x = (x + result + E) % E; //+
- to->sum = to->x; //+
- to->y = mersenne() % 10000000;
- while (a[to->y] != 0) {
- to->y = mersenne() % 10000000;
- }
- a[to->y]++;
- root = insert(root, to);
- rangeCalc(root);
- result = 0;
- }
- else if (c == '?') {
- cin >> y;
- //y++;
- x %= (E);
- y %= (E);
- pair<Node *, long long> res1 = sum(root, x, y);
- root = res1.first;
- rangeCalc(root);
- result = res1.second;
- cout << result << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement