Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define null NULL
- #define dbg if(0)
- struct splay_tree {
- private:
- struct node {
- int key, sz, m;
- node *l, *r, *p;
- node() {
- l = r = p = null;
- key = sz = m = 0;
- }
- node(int key) {
- this->key = m = key;
- sz = 1;
- l = r = p = null;
- }
- };
- typedef node *tnode;
- node *root;
- inline void set_parent(tnode child, tnode parent) {
- if (child) {
- child->p = parent;
- }
- }
- inline void keep_parent(tnode v) {
- set_parent(v->l, v);
- set_parent(v->r, v);
- }
- inline int get_sz(tnode v) {
- return (v ? v->sz : 0);
- }
- inline int get_min(tnode v) {
- return (v ? v->m : INT_MAX);
- }
- inline void upd(tnode v) {
- if (v) {
- v->sz = 1 + get_sz(v->l) + get_sz(v->r);
- v->m = min(v->key, min(get_min(v->l), get_min(v->r)));
- }
- }
- void rotate(tnode child, tnode parent) {
- tnode gparent = parent->p;
- if (gparent) {
- (gparent->l == parent ? gparent->l : gparent->r) = child;
- }
- if (parent->l == child) {
- parent->l = child->r;
- child->r = parent;
- } else {
- parent->r = child->l;
- child->l = parent;
- }
- keep_parent(child);
- keep_parent(parent);
- upd(parent);
- upd(child);
- child->p = gparent;
- }
- tnode splay(tnode v) {
- if (!v->p)
- return v;
- if (!v->p->p) {
- rotate(v, v->p);
- return v;
- }
- tnode parent = v->p;
- tnode gparent = parent->p;
- if ((parent->l == v) == (gparent->l == parent)) {
- rotate(parent, gparent);
- rotate(v, parent);
- } else {
- rotate(v, parent);
- rotate(v, gparent);
- }
- return splay(v);
- }
- tnode find(tnode v, int key) {
- if (!v)
- return null;
- if (get_sz(v->l) < key) {
- key -= get_sz(v->l);
- } else {
- return find(v->l, key);
- }
- if (key == 1) {
- return splay(v);
- }
- return find(v->r, key - 1);
- }
- void split(tnode t, int key, tnode &l, tnode &r) {
- if (!t) {
- l = r = null;
- return;
- }
- if(key == 0){
- l = null;
- r = t;
- return;
- }
- if(key == get_sz(t)){
- l = t;
- r = null;
- return;
- }
- t = find(t, key + 1);
- l = t->l;
- r = t;
- r->l = null;
- set_parent(l, null);
- upd(l);
- upd(r);
- }
- tnode merge(tnode l, tnode r) {
- if (!l)
- return r;
- if (!r)
- return l;
- r = find(r, 1);
- assert(get_sz(r->l) == 0);
- r->l = l;
- l->p = r;
- upd(r);
- return r;
- }
- inline int _get_min(int l, int r) {
- tnode t1, t2, t3;
- split(root, r, t2, t3);
- split(t2, l - 1, t1, t2);
- int ans = t2->m;
- root = merge(t1, t2);
- root = merge(root, t3);
- return ans;
- }
- inline void _add(int pos, int val) {
- tnode t1, t2 = new node(val), t3;
- split(root, pos, t1, t3);
- root = merge(t1, t2);
- root = merge(root, t3);
- }
- void print(tnode t){
- if(!t)
- return;
- print(t->l);
- cout << t->key << " ";
- print(t->r);
- }
- public:
- splay_tree() {
- root = null;
- }
- int get_min(int l, int r){
- return _get_min(l, r);
- }
- void add(int pos, int val){
- _add(pos, val);
- }
- void print(){
- print(root);
- cout << endl;
- }
- };
- #define endl "\n"
- int main(int argc, char **argv) {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n;
- scanf("%d\n",&n);
- splay_tree tree;
- while(n--){
- char c;
- int a, b;
- scanf("%c%d%d\n",&c,&a,&b);
- if(c == '+'){
- tree.add(a, b);
- }else{
- int ans = tree.get_min(a, b);
- printf("%d\n", ans);
- }
- dbg cout << "$$$$ " << n << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement