Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct node{
- int v, w, sz, sum;
- node *l, *r;
- bool rev;
- node(int v_=0){
- v = sum = v_;
- w = rand();
- sz = 1;
- l = r = nullptr;
- rev = false;
- }
- };
- inline int sz(node *t){
- return t ? t->sz : 0;
- }
- inline int sum(node *t){
- return t ? t->sum : 0;
- }
- inline void flush(node *t){
- if(!t || !t->rev) return;
- swap(t->l, t->r);
- if(t->l) t->l->rev ^= 1;
- if(t->r) t->r->rev ^= 1;
- }
- inline void update(node *t){
- if(t == nullptr) return;
- t->sz = sz(t->l) + sz(t->r) + 1;
- t->sum = sum(t->l) + sum(t->r) + t->v;
- }
- inline void merge(node*& t, node *l, node *r){
- if(!l || !r) return void(t = l?l:r);
- flush(l), flush(r);
- if(l->w >= r->w){
- merge(l->r, l->r, r);
- t = l;
- }else{
- merge(r->l, l, r->l);
- t = r;
- }
- update(t);
- }
- inline void split(node *t, node*& l, node*& r, int p){
- if(!t) return void(l = r = nullptr);
- flush(t);
- int pos = sz(t->l) + 1;
- if(pos < p){
- l = t;
- split(t->r, t->r, r, p-pos);
- }else{
- r = t;
- split(t->l, l, t->l, p);
- }
- update(t);
- }
- inline void insert(node*& t, int p, int v){
- node *l=0, *r=0, *aux= new node(v);
- split(t, l, r, p);
- merge(l, l, aux);
- merge(t, l, r);
- }
- inline void erase(node*& t, int p){
- node *l=0, *r=0, *aux=0;
- split(t, l, r, p);
- split(r, aux, r, 2);
- merge(t, l, r);
- delete aux;
- }
- inline int query(node*& t, int l, int r){
- node *a=0, *b=0, *aux=0;
- split(t, a, b, r+1);
- split(a, aux, a, l);
- int ans = sum(a);
- merge(a, aux, a);
- merge(t, a, b);
- return ans;
- }
- inline void reverse(node*& t, int l, int r){
- node *a=0, *b=0, *aux=0;
- split(t, a, b, r+1);
- split(a, aux, a, l);
- a->rev ^= 1;
- merge(a, aux, a);
- merge(t, a, b);
- }
- ostream& operator<<(ostream& out, node *t){
- flush(t);
- if(t) out << t->l << t->v << " " << t->r;
- return out;
- }
- int main(){
- node *t=0;
- int n;
- cin >> n;
- for(int i=1;i<=n;i++){
- int x;
- cin >> x;
- insert(t, i, x);
- }
- cout << t << "\n";
- reverse(t, 2, 3);
- cout << t << "\n";
- return 0;
- }
Add Comment
Please, Sign In to add comment