POJ 3580

#include<bits/stdc++.h>
using namespace std;
int n,rt,cnt,q,r1,r2,r3,a[100010],r4;
struct node{
	int laz,mn,siz,ch[2],key,val;
	bool tag;
}tree[1000010];
string op;
int make(int x){
	cnt++;
	tree[cnt].laz=tree[cnt].tag=0;
	tree[cnt].siz=1;
	tree[cnt].ch[0]=tree[cnt].ch[1]=0;
	tree[cnt].mn=tree[cnt].key=x;
	tree[cnt].val=rand();
	return cnt;
}
void reverse(int o){
	if(!o)return;
	swap(tree[o].ch[0],tree[o].ch[1]);
	tree[o].tag^=1;
}
void add(int o,int x){
	if(!o)return;
	tree[o].key+=x,tree[o].mn+=x,tree[o].laz+=x;
}
void pushdown(int o){
	if(!o)return;
	if(tree[o].laz){
		add(tree[o].ch[0],tree[o].laz);
		add(tree[o].ch[1],tree[o].laz);
		tree[o].laz=0;
	}
	if(tree[o].tag){
		reverse(tree[o].ch[0]);
		reverse(tree[o].ch[1]);
		tree[o].tag=0;
	}
}
void pushup(int o){
	if(!o)return;
	tree[o].siz=tree[tree[o].ch[0]].siz+tree[tree[o].ch[1]].siz+1;
	tree[o].mn=tree[o].key;
	if(tree[o].ch[0])tree[o].mn=min(tree[o].mn,tree[tree[o].ch[0]].mn);
	if(tree[o].ch[1])tree[o].mn=min(tree[o].mn,tree[tree[o].ch[1]].mn);
}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(tree[x].val<tree[y].val){
		pushdown(x);
		tree[x].ch[1]=merge(tree[x].ch[1],y);
		pushup(x);
		return x;
	}
	else{
		pushdown(y);
		tree[y].ch[0]=merge(x,tree[y].ch[0]);
		pushup(y);
		return y;
	}
}
int build(int l,int r){
	if(l==r){
		return make(a[l]);
	}
	int mid=(l+r)>>1;
	return merge(build(l,mid),build(mid+1,r));
}
void split(int o,int x,int &l,int &r){
	if(!o){
		l=r=0;
		return;
	}
	else pushdown(o);
	if(x>=tree[tree[o].ch[0]].siz+1){
		l=o;
		split(tree[o].ch[1],x-tree[tree[o].ch[0]].siz-1,tree[o].ch[1],r);
	}
	else{
		r=o;
		split(tree[o].ch[0],x,l,tree[o].ch[0]);
	}
	pushup(o);
}
int main(){
	srand(time(0));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	rt=merge(rt,build(1,n));
	scanf("%d",&q);
	while(q--){
		cin>>op;
		if(op=="ADD"){
			int pos,len,x,s,y;
			scanf("%d%d%d",&x,&y,&s);
			pos=x,len=y-x+1;
			split(rt,pos-1,r1,r3);
			split(r3,len,r2,r3);
			add(r2,s);
			rt=merge(merge(r1,r2),r3);
		}
		if(op=="REVERSE"){
			int x,y,pos,len;
			scanf("%d%d",&x,&y);
			pos=x,len=y-x+1;
			split(rt,pos-1,r1,r3);
			split(r3,len,r2,r3);
			reverse(r2);
			rt=merge(merge(r1,r2),r3);
		}
		if(op=="REVOLVE"){
			int x,y,s,pos,len;
			scanf("%d%d%d",&x,&y,&s);
			pos=x,len=y-x+1;
			s%=len;
			split(rt,pos-1,r1,r4);
			split(r4,len-s,r2,r4);
			split(r4,s,r3,r4);
			rt=merge(merge(r1,r3),merge(r2,r4));
		}
		if(op=="INSERT"){
			int pos,x;
			scanf("%d%d",&pos,&x);
			int id=make(x);
			split(rt,pos-1,r1,r2);
			rt=merge(merge(r1,id),r2);
		}
		if(op=="DELETE"){
			int pos;
			scanf("%d",&pos);
			split(rt,pos-1,r1,r3);
			split(r3,1,r2,r3);
			rt=merge(r1,r3);
		}
		if(op=="MIN"){
			int x,y,pos,len;
			scanf("%d%d",&x,&y);
			pos=x,len=y-x+1;
			split(rt,pos-1,r1,r3);
			split(r3,len,r2,r3);
			printf("%d\n",tree[r2].mn);
			merge(merge(r1,r2),r3);
		}
	}
	return 0;
}