Advertisement
cosenza987

Untitled

Oct 28th, 2022
1,259
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.28 KB | None | 0 0
  1. //Слава Україні, Героям слава
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. namespace allocat {
  8.     template<class T, int MAXSIZE> struct array {
  9.         T v[MAXSIZE], *top;
  10.         array() : top(v) {}
  11.         T *alloc(const T &val = T()) {
  12.             return &(*top++ = val);
  13.         }
  14.         void dealloc(T *p) {}
  15.     };
  16.     template<class T, int MAXSIZE> struct stack {
  17.         T v[MAXSIZE], *spot[MAXSIZE], **top;
  18.         stack() {
  19.             for(int i = 0; i < MAXSIZE; i++) {
  20.                 spot[i] = v + i;
  21.             }
  22.             top = spot + MAXSIZE;
  23.         }
  24.         T *alloc(const T &val = T()) {
  25.             return &(**--top = val);
  26.         }
  27.         void dealloc(T *p) {
  28.             *top++ = p;
  29.         }
  30.     };
  31. }
  32.  
  33. namespace splay {
  34.     template<class T> struct node {
  35.         T *f, *c[2];
  36.         int size;
  37.         node() {
  38.             f = c[0] = c[1] = nullptr;
  39.             size = 1;
  40.         }
  41.         void push_down() {}
  42.         void update() {
  43.             size = 1;
  44.             for(int t = 0; t < 2; t++) {
  45.                 if(c[t]) {
  46.                     size += c[t]->size;
  47.                 }
  48.             }
  49.         }
  50.     };
  51.     template<class T> struct reversible_node : node<T> {
  52.         int r;
  53.         reversible_node() : node<T>() {
  54.             r = 0;
  55.         }
  56.         void push_down() {
  57.             node<T>::push_down();
  58.             if(r) {
  59.                 for(int t = 0; t < 2; t++) {
  60.                     if(node<T>::c[t]) {
  61.                         node<T>::c[t]->reverse();
  62.                     }
  63.                     r = 0;
  64.                 }
  65.             }
  66.         }
  67.         void update() {
  68.             node<T>::update();
  69.         }
  70.         void reverse() {
  71.             swap(node<T>::c[0], node<T>::c[1]);
  72.             r = r ^ 1;
  73.         }
  74.     };
  75.     template<class T, int MAXSIZE = (int)5e5, class alloc = allocat::array<T, MAXSIZE + 2>> struct tree {
  76.         alloc pool;
  77.         T *root;
  78.         T *new_node(const T &val = T()) {
  79.             return pool.alloc(val);
  80.         }
  81.         tree() {
  82.             root = new_node();
  83.             root->c[1] = new_node();
  84.             root->size = 2;
  85.             root->c[1]->f = root;
  86.         }
  87.         void rotate(T *n) {
  88.             int v = n->f->c[0] == n;
  89.             T *p = n->f, *m = n->c[v];
  90.             if(p->f) {
  91.                 p->f->c[p->f->c[1] == p] = n;
  92.             }
  93.             n->f = p->f;
  94.             n->c[v] = p;
  95.             p->f = n;
  96.             p->c[v ^ 1] = m;
  97.             if(m) {
  98.                 m->f = p;
  99.             }
  100.             p->update();
  101.             n->update();
  102.         }
  103.         void splay(T *n, T *s = nullptr) {
  104.             while(n->f != s) {
  105.                 T *m = n->f, *l = m->f;
  106.                 if(l == s) {
  107.                     rotate(n);
  108.                 } else if((l->c[0] == m) == (m->c[0] == n)) {
  109.                     rotate(m);
  110.                     rotate(n);
  111.                 } else {
  112.                     rotate(n);
  113.                     rotate(n);
  114.                 }
  115.             }
  116.             if(!s) {
  117.                 root = n;
  118.             }
  119.         }
  120.         int size() {
  121.             return root->size - 2;
  122.         }
  123.         int walk(T *n, int &v, int &pos) {
  124.             n->push_down();
  125.             int s = n->c[0] ? n->c[0]->size : 0;
  126.             (v = s < pos) && (pos -= s + 1);
  127.             return s;
  128.         }
  129.         void insert(T *n, int pos) {
  130.             T *c = root;
  131.             int v;
  132.             pos++;
  133.             while(walk(c, v, pos), c->c[v] and (c = c->c[v]));
  134.             c->c[v] = n;
  135.             n->f = c;
  136.             splay(n);
  137.         }
  138.         T *find(int pos, int sp = true) {
  139.             T *c = root;
  140.             int v;
  141.             pos++;
  142.             while((pos < walk(c, v, pos) or v) and (c = c->c[v]));
  143.             if(sp) {
  144.                 splay(c);
  145.             }
  146.             return c;
  147.         }
  148.         T *find_range(int posl, int posr) {
  149.             T *r = find(posr), *l = find(posl - 1, false);
  150.             splay(l, r);
  151.             if(l->c[1]) {
  152.                 l->c[1]->push_down();
  153.             }
  154.             return l->c[1];
  155.         }
  156.         void insert_range(T **nn, int nn_size, int pos) {
  157.             T *r = find(pos), *l = find(pos - 1, false), *c = l;
  158.             splay(l, r);
  159.             for(int i = 0; i < nn_size; i++) {
  160.                 c->c[1] = nn[i];
  161.                 nn[i]->f = c;
  162.                 c = nn[i];
  163.             }
  164.             for(int i = nn_size - 1; i >= 0; i--) {
  165.                 nn[i]->update();
  166.             }
  167.             l->update(), r->update(), splay(nn[nn_size - 1]);
  168.         }
  169.         void dealloc(T *n) {
  170.             if(!n) {
  171.                 return;
  172.             }
  173.             dealloc(n->c[0]);
  174.             dealloc(n->c[1]);
  175.             pool.dealloc(n);
  176.         }
  177.         void erase_range(int posl, int posr) {
  178.             T *n = find_range(posl, posr);
  179.             n->f->c[1] = nullptr, n->f->update(), n->f->f->update(), n->f = nullptr;
  180.             dealloc(n);
  181.         }
  182.     };
  183. }
  184.  
  185. const int N = 2e5 + 7;
  186.  
  187. struct node: splay::reversible_node<node> {
  188.     long long val, val_min, lazy;
  189.     node(long long v = 0) : splay::reversible_node<node>(), val(v) {
  190.         val_min = lazy = 0;
  191.     }
  192.     void add(long long v) {
  193.         val += v;
  194.         val_min += v;
  195.         lazy += v;
  196.     }
  197.     void push_down() {
  198.         splay::reversible_node<node>::push_down();
  199.         for(int t = 0; t < 2; t++) {
  200.             if(c[t]) {
  201.                 c[t]->add(lazy);
  202.             }
  203.         }
  204.         lazy = 0;
  205.     }
  206.     void update() {
  207.         splay::reversible_node<node>::update();
  208.         val_min = val;
  209.         for(int t = 0; t < 2; t++) {
  210.             if(c[t]) {
  211.                 val_min = min(val_min, c[t]->val_min);
  212.             }
  213.         }
  214.     }
  215. };
  216.  
  217. splay::tree<node, N, allocat::stack<node, N + 2>> t;
  218.  
  219. int main() {
  220.     ios_base::sync_with_stdio(false);
  221.     cin.tie(nullptr);
  222.     int n, q;
  223.     cin >> n;
  224.     for(int i = 0; i < n; i++) {
  225.         long long x;
  226.         cin >> x;
  227.         t.insert(t.new_node(node(x)), t.size());
  228.     }
  229.     cin >> q;
  230.     while(q--) {
  231.         string s;
  232.         cin >> s;
  233.         if(s == "ADD") {
  234.             int x, y;
  235.             long long d;
  236.             cin >> x >> y >> d;
  237.             t.find_range(x - 1, y)->add(d);
  238.         }
  239.         if(s == "REVERSE") {
  240.             int x, y;
  241.             cin >> x >> y;
  242.             t.find_range(x - 1, y)->reverse();
  243.         }
  244.         if(s == "REVOLVE") {
  245.             int x, y;
  246.             long long d;
  247.             cin >> x >> y >> d;
  248.             d %= (y - x + 1);
  249.             if(d) {
  250.                 node *right = t.find_range(y - d, y);
  251.                 right->f->c[1] = nullptr, right->f->update(), right->f->f->update(), right->f = nullptr;
  252.                 t.insert(right, x - 1);
  253.             }
  254.         }
  255.         if(s == "INSERT") {
  256.             int x;
  257.             long long p;
  258.             cin >> x >> p;
  259.             t.insert(t.new_node(node(p)), x);
  260.         }
  261.         if(s == "DELETE") {
  262.             int x;
  263.             cin >> x;
  264.             t.erase_range(x - 1, x);
  265.         }
  266.         if(s == "MIN") {
  267.             int x, y;
  268.             cin >> x >> y;
  269.             cout << t.find_range(x - 1, y)->val_min << "\n";
  270.         }
  271.     }
  272.     return 0;
  273. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement