treap_implicita.cpp

#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;
}