Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 6058 Accepted: 1963
Case Time Limit: 2000MS

Description

Your friend, Jackson is invited to a TV show called SuperMemo in which the participant is told to play a memorizing game. At first, the host tells the participant a sequence of numbers, {A1, A2, ... An}. Then the host performs a series of operations and queries on the sequence which consists:

  1. ADD x y D: Add D to each number in sub-sequence {Ax ... Ay}. For example, performing "ADD 2 4 1" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5, 5}
  2. REVERSE x y: reverse the sub-sequence {Ax ... Ay}. For example, performing "REVERSE 2 4" on {1, 2, 3, 4, 5} results in {1, 4, 3, 2, 5}
  3. REVOLVE x y T: rotate sub-sequence {Ax ... Ay} T times. For example, performing "REVOLVE 2 4 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 2, 5}
  4. INSERT x P: insert P after Ax. For example, performing "INSERT 2 4" on {1, 2, 3, 4, 5} results in {1, 2, 4, 3, 4, 5}
  5. DELETE x: delete Ax. For example, performing "DELETE 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5}
  6. MIN x y: query the participant what is the minimum number in sub-sequence {Ax ... Ay}. For example, the correct answer to "MIN 2 4" on {1, 2, 3, 4, 5} is 2

To make the show more interesting, the participant is granted a chance to turn to someone else that means when Jackson feels difficult in answering a query he may call you for help. You task is to watch the TV show and write a program giving the correct answer to each query in order to assist Jackson whenever he calls.

Input

The first line contains n (n ≤ 100000).

The following n lines describe the sequence.

Then follows M (M ≤ 100000), the numbers of operations and queries.

The following M lines describe the operations and queries.

Output

For each "MIN" query, output the correct answer.

Sample Input

5
1 
2 
3 
4 
5
2
ADD 2 4 1
MIN 4 5

Sample Output

5
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<algorithm>
using namespace std;
#define N 2000010
#define inf 0x3fffffff
class node{
public:
	int key,sz,mn,lz,rev,x;
	node* ch[2];
	void init(int k){
		mn=key=k;sz=1;x=rand();//随机树起，父的x比儿子的x小
		lz=rev=0;ch[0]=ch[1]=null;
	}
	void update(){
		if(this==null)return;
		sz=ch[0]->sz+ch[1]->sz+1;
		mn=min(key,min(ch[0]->mn+ch[0]->lz,ch[1]->mn+ch[1]->lz));
	}
	void down(){
		if(this==null)return;
		if(rev){
			swap(ch[0],ch[1]);
			ch[0]->rev^=1;ch[1]->rev^=1;rev=0;
		}
		if(lz){
			key+=lz;mn+=lz;
			ch[0]->lz+=lz;ch[1]->lz+=lz;lz=0;
		}
		null->init(inf);null->x=inf;null->sz=0;
	}
}a[N],*root,*null=a,*cnt;
class Treap{
public:
	Treap(){
	null->init(inf);null->x=inf;null->sz=0;root=cnt=a;
	}
	void rotate(node*& x,int i){//0左旋 1右旋
		int j=i^1;
		node* y=x->ch[i];
		y->down();
		x->ch[i]=y->ch[j];
		y->ch[j]=x;
		x->update();
		x=y;
		//x->update;//后面会更新
	}
	void insert(node*& x,int k,int v){//第k名插入v
		if(x==null){
			x=++cnt;x->init(v);
			return;
		}
		x->down();
		int i;
		if(x->ch[0]->sz>=k)i=0;//当前大于k，往左
		else{//不大于k,往右
			i=1;
			k=k-x->ch[0]->sz-1;
		}
		insert(x->ch[i],k,v);
		if(x->x>x->ch[i]->x)rotate(x,i);//把儿子x小的变成父结点
		x->update();
	}
	void del(node*& x,int k){
		if(x==null)return;
		x->down();
		if(x->ch[0]->sz==k)merge(x,x->ch[0],x->ch[1]);//当前x为第k+1名,删除x
		else if(x->ch[0]->sz>k)del(x->ch[0],k);
		else del(x->ch[1],k-x->ch[0]->sz-1);
		x->update();
	}
	void cut(node* x,node*& l,node*& r,int k){//将x第k名之前cut到l中[0,k]，k名之后cut到r中[k+1,n]
		if(k==0){l=null;r=x;return;}//当前x中全比k大
		if(x->sz==k){l=x;r=null;return;}//当前x中全比k+1小
		x->down();
		if(x->ch[0]->sz>=k){//当前x大于k,x加入r,l不变,拆分左子树x->ch[0]
			x->ch[0]->down();
			r=x;
			cut(x->ch[0],l,r->ch[0],k);
			r->update();
		}else{//当前x小于k,加入l,r不变,拆分右子树x->ch[1]
			x->ch[1]->down();
			l=x;
			cut(x->ch[1],l->ch[1],r,k-x->ch[0]->sz-1);
			l->update();
		}
	}
	void merge(node*& x,node* l,node* r){//l r合并到x中(l中所有元素小于r中的元素)
		if(l==null){x=r;return;}
		if(r==null){x=l;return;}
		if(l->x<r->x){//随机权值小的为父结点
			l->down();
			merge(l->ch[1],l->ch[1],r);
			l->update();
			x=l;
		}else{
			r->down();
			merge(r->ch[0],l,r->ch[0]);
			r->update();
			x=r;
		}
	}
	//-----------------------------------------------------//
	void reverse(int a,int b){
	  node *x,*l,*r;
	  cut(root,x,l,a);//root中大于a的放到l,则放到x,l->[a+1,n]
	  cut(l,l,r,b-a+1);//l中大于b的放到r,则放到l,l->[a+1,b+1]
	  l->rev^=1;
	  merge(x,x,l);//x<l<r
	  merge(root,x,r);
	}
	void revolve(int a,int b,int c){//交换区间[a,b],[b+1,c]
	  node *x,*l,*r,*s;
	  cut(root,x,l,a);//root中大于i的放到l,则放到x,l->[i,n]
	  cut(l,l,r,b-a+1);//x中大于j的放到r,则放到l,l->[i,j]
	  cut(r,r,s,c-b);//把r大于k的cut到r里,刚放到s,r->[j+1,k]
			//x:[0,i-1] l:[i,j]  r:[j+1,k] s:[k+1,n]
	  merge(x,x,r);//x r合并到x
	  merge(x,x,l);//x,l合并到x
	  merge(root,x,s);//x,s合并到root

	}
	void add(int a,int b,int k){
	  node *x,*l,*r;
	  cut(root,x,l,a);//root中大于i-1的放到l,则放到x,l->[i-1,n]
	  cut(l,l,r,b-a+1);//x中大于j-i+1的放到r,则放到l,l->[i-1,j-1]
	  l->lz+=k;
	  merge(x,x,l);//x<l<r
	  merge(root,x,r);
	}
	void getmin(int a,int b){
	  node *x,*l,*r;
	  cut(root,x,l,a);//root中大于i-1的放到l,则放到x,l->[i-1,n]
	  cut(l,l,r,b-a+1);//x中大于j-i+1的放到r,则放到l,l->[i-1,j-1]
	  printf("%d\n",l->mn);
	  merge(x,x,l);//x<l<r
	  merge(root,x,r);
	}
	void print(node* x,int d){
		if(x==null)return;
		x->down();
		print(x->ch[0],d+1);
		printf("%d(%d) ",x->key,d);
		print(x->ch[1],d+1);
	}
};
/*****************************************************/
int main()
{
	Treap treap;
	int n,i,j,k;
	char s[30];
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&j);
		treap.insert(root,i,j);
	}
	scanf("%d",&n);
	while(n--){
		//treap.print(root,1);cout<<endl;
		scanf("%s",s);
		if(s[0]=='A')
		{
			scanf("%d%d%d",&i,&j,&k);
			treap.add(i-1,j-1,k);
		}else if(s[0]=='I')
		{
			scanf("%d%d",&i,&k);
			treap.insert(root,i,k);
		}else if(s[0]=='D')
		{
			scanf("%d",&i);
			treap.del(root,i-1);
		}else if(s[0]=='M')
		{
			scanf("%d%d",&i,&j);
			treap.getmin(i-1,j-1);

		}else if(s[3]=='E')
		{
			scanf("%d%d",&i,&j);
			treap.reverse(i-1,j-1);//反转区间[i,j];
		}else //交换[i,i+k],[i+k+1,j]
		{
			scanf("%d%d%d",&i,&j,&k);
			i--;j--;
			k%=(j-i+1);
			k+=(j-i+1);
			k%=(j-i+1);
			if(k)treap.revolve(i,j-k,j);
		}
	}
return 0;
}

更多推荐

poj 3580 SuperMemo(Treap平衡树解法)