POJ 3580 Splay - c++编程基础

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: acvcla@gmail.com
    > 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(

POJ 3580 Splay(一)