裸Splay區間操作: 內存池+區間加減+區間翻轉+插入+刪除+維護最值
SuperMemo
Time Limit: 5000MS
Memory Limit: 65536K
Total Submissions: 8552
Accepted: 2801
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:
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
5
1
2
3
4
5
2
ADD 2 4 1
MIN 4 5
Sample Output
5
Source
POJ Founder Monthly Contest – 2008.04.13, Yao Jinyu
[Submit] [Go Back] [Status]
[Discuss]
#include
#include
#include
#include
using namespace std;
const int maxn=220000;
const int INF=0x3f3f3f3f;
#define Key_Value ch[ch[root][1]][0]
int ch[maxn][2],rev[maxn],add[maxn],sz[maxn],pre[maxn],key[maxn],minn[maxn];
int root,tot1;
int s[maxn],tot2;
int n,q,a[maxn];
void NewNode(int& x,int father,int k)
{
if(tot2) x=s[tot2--];
else x=++tot1;
ch[x][0]=ch[x][1]=rev[x]=add[x]=0;
sz[x]=1; pre[x]=father; key[x]=minn[x]=k;
}
void Erase(int r)
{
if(r)
{
s[++tot2]=r;
Erase(ch[r][0]);
Erase(ch[r][1]);
}
}
void Upd_Rev(int x)
{
if(!x) return ;
swap(ch[x][0],ch[x][1]);
rev[x]^=1;
}
void Upd_Add(int x,int d)
{
if(!x) return ;
key[x]+=d; minn[x]+=d;
add[x]+=d;
}
void Push_Up(int x)
{
sz[x]=sz[ch[x][1]]+sz[ch[x][0]]+1;
minn[x]=key[x];
if(ch[x][0]) minn[x]=min(minn[x],minn[ch[x][0]]);
if(ch[x][1]) minn[x]=min(minn[x],minn[ch[x][1]]);
}
void Push_Down(int x)
{
if(rev[x])
{
Upd_Rev(ch[x][0]); Upd_Rev(ch[x][1]);
rev[x]=0;
}
if(add[x])
{
Upd_Add(ch[x][0],add[x]); Upd_Add(ch[x][1],add[x]);
add[x]=0;
}
}
void Build(int& x,int l,int r,int fa)
{
if(l>r) return ;
int mid=(l+r)/2;
NewNode(x,fa,a[mid]);
Build(ch[x][0],l,mid-1,x);
Build(ch[x][1],mid+1,r,x);
Push_Up(x);
}
void Init()
{
root=tot1=tot2=0;
ch[root][0]=ch[root][1]=pre[root]=sz[root]=0;
minn[root]=key[root]=INF;
NewNode(root,0,INF);
NewNode(ch[root][1],root,INF);
Build(Key_Value,1,n,ch[root][1]);
Push_Up(ch[root][1]);
Push_Up(root);
}
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]][1]==y]=x;
pre[x]=pre[y];
pre[y]=x;
ch[x][kind]=y;
Push_Up(y);
}
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]][0]==r);
}
else
{
Push_Down(pre[pre[r]]);
Push_Down(pre[r]);
Push_Down(r);
int y=pre[r];
int kind=(ch[pre[y]][0]==y);
if(ch[y][kind]==r) Rotate(r,!kind);
else Rotate(y,kind);
Rotate(r,kind);
}
}
Push_Up(r);
if(goal==0) root=r;
}
int Get_Kth(int r,int k)
{
Push_Down(r);
int t=sz[ch[r][0]]+1;
if(k==t) return r;
if(t
