程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3580 Splay

POJ 3580 Splay

編輯：C++入門知識

POJ 3580 Splay

G - SuperMemo Time Limit:5000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status Practice POJ 3580 Appoint description:

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, {A₁, A₂, ... A_n}. Then the host performs a series of operations and queries on the sequence which consists:

ADD x y D: Add D to each number in sub-sequence {A_x ... A_y}. For example, performing "ADD 2 4 1" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5, 5}REVERSE x y: reverse the sub-sequence {A_x ... A_y}. For example, performing "REVERSE 2 4" on {1, 2, 3, 4, 5} results in {1, 4, 3, 2, 5}REVOLVE x y T: rotate sub-sequence {A_x ... A_y} T times. For example, performing "REVOLVE 2 4 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 2, 5}INSERT x P: insert P after A_x. For example, performing "INSERT 2 4" on {1, 2, 3, 4, 5} results in {1, 2, 4, 3, 4, 5}DELETE x: delete A_x. For example, performing "DELETE 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5}MIN x y: query the participant what is the minimum number in sub-sequence {A_x ... A_y}. 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

Sample Output

初始時給出一個序列，進行一下操作：

ADD x y D [x,y] 區間每個元素增加D

REVERSE x y 翻轉區間[x,y]

REVOLVE x y t 區間[x,y]循環右移t位。

INSERT x p 在x之後插入p

DELETE x 刪除元素x

MIN x y 詢問區間[x,y]的最小值

注意REVOLVE 可以轉化成3次REVERSE或者一次

ADD 和RECERSE采用lazy標記，每次更新兩層

代碼：

/*************************************************************************
    > File Name: Spaly.cpp
    > Author: acvcla
    > QQ:
    > Mail: [email protected]
    > Created Time: 2014Äê11ÔÂ16ÈÕ ÐÇÆÚÈÕ 00Ê±14·Ö26Ãë
 ************************************************************************/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 100;
const int inf=1e9+7;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
int ch[maxn][2],pre[maxn],rev[maxn],siz[maxn],Min[maxn];
int root,tot;
int addv[maxn],A[maxn],tmp[maxn];
void newnode(int &x,int fa,int k)
{
	x=++tot;
	A[x]=k;
	Min[x]=k;
	siz[x]=1;
	pre[x]=fa;
	addv[x]=rev[x]=ch[x][1]=ch[x][0]=0;
}
void push_up(int x){
	if(!x)return;
	siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
	Min[x]=min(Min[ch[x][0]],Min[ch[x][1]]);
	Min[x]=min(Min[x],A[x]);
}
void upadte_rev(int x)
{
	if(!x)return ;
	swap(ch[x][0],ch[x][1]);
	rev[x]^=1;
}
void Modify(int x,int val){
	if(!x)return;
	A[x]+=val;
	Min[x]+=val;
	addv[x]+=val;
}
void push_down(int x)
{
	if(!x)return;
	if(addv[x]){
		Modify(ch[x][0],addv[x]);
		Modify(ch[x][1],addv[x]);
		addv[x]=0;
	}
	if(rev[x]){
		upadte_rev(ch[x][0]);
		upadte_rev(ch[x][1]);
		rev[x]^=1;
	}
}
void Rotate(int x,int kind)
{
	int y=pre[x];
	push_down(y);
	push_down(x);
	ch[y][!kind]=ch[x][kind];
	pre[ch[x][kind]]=y;
	ch[x][kind]=y;

	if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;
	pre[x]=pre[y];
	pre[y]=x;
	push_up(y);
	push_up(x);
}
void Splay(int x,int goal)
{
	while(pre[x]!=goal){
		if(pre[pre[x]]==goal)Rotate(x,ch[pre[x]][0]==x);
		else{
			int y=pre[x];
			int kind=(ch[pre[y]][0]==y);
			if(ch[y][kind]==x){
				Rotate(x,!kind);
				Rotate(x,kind);
			}else{
				Rotate(y,kind);
				Rotate(x,kind);
			}
		}
	}
	if(goal==0)root=x;
}
void built(int &x,int L,int R,int fa)
{
	if(L>R)return;
	int mid=(R+L)>>1;
	newnode(x,fa,tmp[mid]);
	built(ch[x][0],L,mid-1,x);
	built(ch[x][1],mid+1,R,x);
	push_up(x);
}
void init(int n)
{
	siz[0]=pre[0]=0;
	root=tot=ch[0][0]=ch[0][1]=0;
	Min[0]=inf;
	newnode(root,0,inf);
	newnode(ch[root][1],root,inf);
	for(int i=1;i<=n;i++)scanf("%d",tmp+i);
	built(ch[ch[root][1]][0],1,n,ch[root][1]);
	push_up(ch[root][1]);
	push_up(root);
}
int Get_kth(int x,int k){
	push_down(x);
	int sz=siz[ch[x][0]]+1;
	if(sz==k)return x;
	if(sz>k)return Get_kth(ch[x][0],k);
	return Get_kth(ch[x][1],k-sz);
}
int Get_max(int x)
{
	push_down(x);
	while(ch[x][1])
	{
		x=ch[x][1];
		push_down(x);
	}
	return x;
}
void add(int L,int R,int v)
{
	Splay(Get_kth(root,L-1),0);
	Splay(Get_kth(root,R+1),root);
	Modify(ch[ch[root][1]][0],v);
}
void reverse(int L,int R)
{
	Splay(Get_kth(root,L-1),0);
	Splay(Get_kth(root,R+1),root);
	upadte_rev(ch[ch[root][1]][0]);
}
void revolve(int L,int R,int c)
{
    c  %= (R-L+1);
    if (!c)return;
	reverse(L,R);
    reverse(L,L+c-1);
    reverse(L+c,R);
}
void Insert(int x,int p)
{
	Splay(Get_kth(root,x),0);
	Splay(Get_kth(root,x+1),root);
	newnode(ch[ch[root][1]][0],ch[root][1],p);
	push_up(ch[root][1]);
	push_up(root);
}
void remove_root()
{
	push_down(root);
	if(!ch[root][0]){
		root=ch[root][1];
	}else{
		int t=Get_max(ch[root][0]);
		Splay(t,root);
		ch[t][1]=ch[root][1];
		pre[ch[root][1]]=t;
		root=t;
	}
	pre[root]=0;
	push_up(root);
}
void del(int x)
{
	Splay(Get_kth(root,x),0);
	remove_root();
}
int Query(int L,int R)
{
	Splay(Get_kth(root,L-1),0);
	Splay(Get_kth(root,R+1),root);
	return Min[ch[ch[root][1]][0]];
}
int main(int argc, char const *argv[])
{
		int n,m,L,R,x;
		scanf("%d",&n);
		init(n);
		scanf("%d",&m);
		char op[10];
		while(m--){
			scanf("%s",op);
			if(op[0]=='A'){
				scanf("%d%d%d",&L,&R,&x);
				add(L+1,R+1,x);
			}else if(op[0]=='D'){
				scanf("%d",&L);
				del(L+1);
			}else if(op[0]=='I'){
				scanf("%d%d",&L,&x);
				Insert(L+1,x);
			}else if(op[0]=='M'){
				scanf("%d%d",&L,&R);
				printf("%d\n",Query(L+1,R+1));
			}else if(op[0]=='R'){
				if(op[3]=='E'){
					scanf("%d%d",&L,&R);
					reverse(L+1,R+1);
				}else{
					scanf("%d%d%d",&L,&R,&x);
					revolve(L+1,R+1,x);
				}
			}
		}
		return 0;
}