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:
- 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}
- 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}
- 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}
- 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}
- DELETE x: delete Ax. 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 {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
ADD
MIN
Sample Output
Source
POJ Founder Monthly Contest – 2008.04.13, Yao Jinyu
一道splay模板题。要求你设计一个数据结构实现以下操作：
1）Add(l,r,d)向区间l~r中的元素加上一个数d；
2）Reverse(l,r)翻转区间l~r的元素；
3）Revolve(l,r,T)将区间l~r的后缀放到区间的前方，操作T次；
4）Insert(x,P)将元素P插入到元素x后方；
5）Delete(x)删除元素x；
6）Min(l,r)求区间l~r中的最小值；
因为操作和题目需要，我们建立三个虚根，0、root（在NewNode操作后，root初始值为1）和root的右孩子（即ch[root][1]），一个实根，root的右孩子的左孩子（即ch[ch[root][1]][0]，Key_value的初始值）。
一道splay模板题。要求你设计一个数据结构实现以下操作：
1）Add(l,r,d)向区间l~r中的元素加上一个数d；
2）Reverse(l,r)翻转区间l~r的元素；
3）Revolve(l,r,T)将区间l~r的后缀放到区间的前方，操作T次；
4）Insert(x,P)将元素P插入到元素x后方；
5）Delete(x)删除元素x；
6）Min(l,r)求区间l~r中的最小值；
因为操作和题目需要，我们建立三个虚根，0、root（在NewNode操作后，root初始值为1）和root的右孩子（即ch[root][1]），一个实根，root的右孩子的左孩子（即ch[ch[root][1]][0]，Key_value的初始值）。
#include<cstdio>
#include<iostream>
#define INF 0x3f3f3f3f
#define Key_value ch[ch[root][1]][0]
using namespace std;
bool rev[];
int n,tot,root,a[],key[],add[],pre[],ch[][],size[],minn[];
inline void Update_Add(int r,int d)
{
if(!r)return;
add[r]+=d;
key[r]+=d;
minn[r]+=d;
}
inline void Update_Reve(int r)
{
if(!r)return;
rev[r]^=;
swap(ch[r][],ch[r][]);
}
inline void Push_Up(int k)
{
minn[k]=min(key[k],min(minn[ch[k][]],minn[ch[k][]]));
size[k]=size[ch[k][]]+size[ch[k][]]+;
}
inline void Push_Down(int r)
{
if(add[r]){
Update_Add(ch[r][],add[r]);
Update_Add(ch[r][],add[r]);
add[r]=;
}
if(rev[r]){
Update_Reve(ch[r][]);
Update_Reve(ch[r][]);
rev[r]=;
}
}
inline int Get_Kth(int r,int k)
{
Push_Down(r);
int t=size[ch[r][]]+;
if(t==k)return r;
if(t>k)return Get_Kth(ch[r][],k);
else return Get_Kth(ch[r][],k-t);
}
inline void NewNode(int &r,int father,int val)
{
r=++tot;
size[r]=;
pre[r]=father;
key[r]=minn[r]=val;
}
inline void Build(int &x,int father,int l,int r)
{
if(l>r)return;
int mid=(l+r)>>;
NewNode(x,father,a[mid]);
Build(ch[x][],x,l,mid-);
Build(ch[x][],x,mid+,r);
Push_Up(x);
}
inline void Init()
{
root=tot=;
minn[root]=INF;
ch[root][]=ch[root][]=pre[root]=add[root]=rev[root]=size[root]=;
NewNode(root,,INF);
NewNode(ch[root][],root,INF);
Build(Key_value,ch[root][],,n);
}
inline 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;
if(pre[y])ch[pre[y]][ch[pre[y]][]==y]=x;
pre[x]=pre[y];
ch[x][kind]=y;
pre[y]=x;
Push_Up(y);
}
inline void Splay(int r,int goal)
{
Push_Down(r);
while(pre[r]!=goal){
if(pre[pre[r]]==goal){
Push_Down(pre[r]);
Push_Down(r);
Rotate(r,ch[pre[r]][]==r);
}
else{
int y=pre[r];
int kind=ch[pre[y]][]==y;
Push_Down(pre[y]);
Push_Down(y);
Push_Down(r);
if(ch[y][kind]==r){
Rotate(r,!kind);
Rotate(r,kind);
}
else{
Rotate(y,kind);
Rotate(r,kind);
}
}
}
Push_Up(r);
if(!goal)root=r;
}
inline void Add(int l,int r,int d)
{
Splay(Get_Kth(root,l),);//调用Get_Kth()首参数要用root因为root可能变成区间内其他数;
Splay(Get_Kth(root,r+),root);
Update_Add(Key_value,d);
Push_Up(ch[root][]);
Push_Up(root);
}
inline int Min(int l,int r)
{
Splay(Get_Kth(root,l),);//ADD注释+1;
Splay(Get_Kth(root,r+),root);
return minn[Key_value];
}
inline void Del(int x)
{
Splay(Get_Kth(root,x),);
Splay(Get_Kth(root,x+),root);
pre[Key_value]=;
Key_value=;//直接清零即可;
Push_Up(ch[root][]);
Push_Up(root);
}
inline void Reve(int l,int r)
{
Splay(Get_Kth(root,l),);
Splay(Get_Kth(root,r+),root);
Update_Reve(Key_value);
Push_Up(ch[root][]);
Push_Up(root);
}
inline void Revo(int a,int b,int t)
{
int c=b-t;//将区间a~b分为两个区间a~b-c、b-c+1~b，将区间2旋转到区间1前;
Splay(Get_Kth(root,a),);
Splay(Get_Kth(root,c+),root);
int tmp=Key_value;
Key_value=;
Push_Up(ch[root][]);
Push_Up(root);
Splay(Get_Kth(root,b-c+a),);
Splay(Get_Kth(root,b-c+a+),root);
Key_value=tmp;
pre[Key_value]=ch[root][];
Push_Up(ch[root][]);
Push_Up(root);
}
inline void Ins(int x,int t)
{
Splay(Get_Kth(root,x+),);
Splay(Get_Kth(root,x+),root);
NewNode(Key_value,ch[root][],t);
Push_Up(ch[root][]);
Push_Up(root);
}
int main()
{
while(scanf("%d",&n)!=EOF){
for(int i=;i<=n;i++)scanf("%d",&a[i]);
Init();
int Case;
scanf("%d",&Case);
for(;Case;Case--){
char order[];
scanf("%s",order);
if(order[]=='A'){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
Add(x,y,z);
}
if(order[]=='M'){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",Min(x,y));
}
if(order[]=='D'){
int x;
scanf("%d",&x);
Del(x);
}
if(order[]=='I'){
int x,t;
scanf("%d%d",&x,&t);
Ins(x,t);
}
if(order[]=='R'&&order[]=='E'){
int x,y;
scanf("%d%d",&x,&y);
Reve(x,y);
}
if(order[]=='R'&&order[]=='O'){
int x,y,T;
scanf("%d%d%d",&x,&y,&T);
Revo(x,y,(T%(y-x+)+y-x+)%(y-x+));
}
}
}
return ;
}