Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- #include <map>
- #include <set>
- using namespace std;
- class Treap {
- private:
- struct node {
- node *left, *right;
- int x, y;
- int cost, size;
- long long add, sum;
- node () {left = right = NULL; cost = sum = add = 0ll, size = 0;}
- node (int X, int Y, int COST) {left = right = NULL; x = X, y = Y, cost = COST, sum = 0ll, size = 1, add = 0ll; }
- };
- node *treap;
- void split (node* T, node*& L, node*& R, int x);
- void merge (node* L, node* R, node *& T);
- void recalc (node*& T);
- long long sumOf (node* T) {return T ? T->sum : 0ll;};
- int sizeOf (node* T) {return T ? T->size : 0; }
- void push (node*& T);
- public:
- Treap () {treap = NULL; }
- void add (int cost);
- long long get (int l, int r);
- void update (int l, int r, int dx);
- int size () {return sizeOf(treap); }
- int sum () {return sumOf (treap); }
- };
- void Treap :: recalc (node*& T) {
- if (T) {
- T->size = sizeOf (T->left) + sizeOf (T->right) + 1;
- T->sum = sumOf (T->left) + sumOf (T->right) + T->cost;
- }
- }
- void Treap :: push (node*& T) {
- if (T) {
- if (T->right)
- T->right->add += T->add;
- if (T->left)
- T->left->add += T->add;
- T->sum += T->add * T->size;
- T->add = 0ll;
- }
- }
- void Treap :: split (node* T, node*& L, node*& R, int x) {
- if (!T) {
- L = R = NULL;
- return;
- }
- push (T);
- if (T->x < x) {
- L = T;
- split (T->right, L->right, R, x);
- recalc (L);
- } else {
- R = T;
- split (T->left, L, R->left, x);
- recalc (R);
- }
- }
- void Treap :: merge (node* L, node* R, node*& T) {
- push (L);
- push (R);
- if (!L || !R) {
- T = L ? L : R;
- return;
- }
- if (L->y > R->y) {
- T = L;
- merge (L->right, R, T->right);
- } else {
- T = R;
- merge (L, R->left, T->left);
- }
- recalc (T);
- }
- void Treap :: add (int cost) {
- if (!treap) {
- treap = new node (1, rand(), cost);
- return;
- }
- int x = sizeOf(treap) + 1;
- node *M = new node (x, rand(), cost);
- node *L, *R;
- split (treap, L, R, x);
- merge (L, M, L);
- merge (L, R, treap);
- }
- long long Treap :: get (int l, int r) {
- node *L = 0, *R = 0, *M = 0, *N = 0;
- split (treap, L, R, l);
- split (R, N, M, r + 1);
- long long res = sumOf (N);
- merge (N, M, R);
- merge (L, R, treap);
- return res;
- }
- void Treap :: update (int l, int r, int dx) {
- node *L = 0, *R = 0, *M = 0, *N = 0;
- split (treap, L, R, l);
- split (R, N, M, r + 1);
- N->add += dx;
- merge (N, M, R);
- merge (L, R, treap);
- }
- Treap myTreap;
- int main () {
- srand (time (0));
- int n;
- cin >> n;
- for (int i = 0; i < n; i++) {
- int c;
- cin >> c;
- myTreap.add (c);
- }
- int m;
- cin >> m;
- while (m--) {
- int l, r, x;
- char ch;
- cin >> ch >> l >> r;
- if (ch == 'g')
- cout << myTreap.get (l, r) << "\n";
- else {
- cin >> x;
- myTreap.update(l, r, x);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement