poj3580 SuperMemo
SuperMemo
Time Limit: 5000MS
Memory Limit: 65536K
Total Submissions: 12273
Accepted: 3887
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
和bzoj1500維修數列有點像，都是Splay維護區間很多操作的題，不過這道題維護的數據比較少。
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define LL long long
#define pa pair
#define MAXN 200005
#define INF 1000000000
#define key c[c[rt][1]][0]
using namespace std;
int n,m,rt,tot,a[MAXN];
int c[MAXN][2],v[MAXN],mn[MAXN],tag[MAXN],fa[MAXN],s[MAXN];
bool rev[MAXN];
char ch[10];
inline int read()
{
int ret=0,flag=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') flag=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
return ret*flag;
}
inline void updateadd(int k,int x)
{
if (!k) return;
tag[k]+=x;mn[k]+=x;v[k]+=x;
}
inline void updaterev(int k)
{
if (!k) return;
rev[k]^=1;swap(c[k][0],c[k][1]);
}
inline void pushdown(int k)
{
int l=c[k][0],r=c[k][1];
if (tag[k]){updateadd(l,tag[k]);updateadd(r,tag[k]);tag[k]=0;}
if (rev[k]){updaterev(l);updaterev(r);rev[k]=0;}
}
inline void pushup(int k)
{
int l=c[k][0],r=c[k][1];
s[k]=s[l]+s[r]+1;
mn[k]=min(min(mn[l],mn[r]),v[k]);
}
inline void travel(int k)
{
if (!k) return;
pushdown(k);
travel(c[k][0]);
printf("%d ",v[k]);
travel(c[k][1]);
}
inline void newnode(int &k,int x,int last)
{
k=++tot;
c[k][0]=c[k][1]=rev[k]=tag[k]=0;
fa[k]=last;
v[k]=mn[k]=x;
s[k]=1;
}
inline void build(int &k,int l,int r,int last)
{
if (l>r) return;
int mid=(l+r)>>1;
newnode(k,a[mid],last);
build(c[k][0],l,mid-1,k);
build(c[k][1],mid+1,r,k);
pushup(k);
}
inline void rotate(int x,int &k)
{
int y=fa[x],z=fa[y],l=(c[y][1]==x),r=l^1;
if (y==k) k=x;
else if (c[z][0]==y) c[z][0]=x;else c[z][1]=x;
fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
pushup(y);
}
inline void splay(int x,int &k)
{
while (x!=k)
{
int y=fa[x],z=fa[y];
if (y!=k)
{
if ((c[y][0]==x)^(c[z][0]==y)) rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
pushup(x);
}
inline int find(int k,int rank)
{
pushdown(k);
int l=c[k][0],r=c[k][1];
if (s[l]+1==rank) return k;
else if (s[l]>=rank) return find(l,rank);
else return find(r,rank-s[l]-1);
}
inline void split(int l,int r)
{
int x=find(rt,l-1),y=find(rt,r+1);
splay(x,rt);splay(y,c[rt][1]);
}
inline void solveadd(int l,int r,int x)
{
split(l,r);
updateadd(key,x);
}
inline void solverev(int l,int r)
{
split(l,r);
updaterev(key);
}
inline void revolve(int l,int r,int x)
{
int cnt=r-l+1,y,tmp;
x=(x%cnt+cnt)%cnt;
if (!x) return;
y=r-x;
split(y+1,r);tmp=key;fa[key]=0;key=0;
pushup(c[rt][1]);pushup(rt);
split(l,l-1);key=tmp;fa[tmp]=c[rt][1];
pushup(c[rt][1]);pushup(rt);
}
inline void solveins(int pos,int x)
{
split(pos+1,pos);
newnode(key,x,c[rt][1]);
pushup(c[rt][1]);pushup(rt);
}
inline void solvedel(int pos)
{
split(pos,pos);
fa[key]=0;key=0;
pushup(c[rt][1]);pushup(rt);
}
inline void getmin(int l,int r)
{
split(l,r);
printf("%d\n",mn[key]);
}
int main()
{
while (scanf("%d",&n)!=EOF)
{
rt=tot=0;
c[rt][0]=c[rt][1]=fa[rt]=rev[rt]=tag[rt]=s[rt]=0;
mn[rt]=INF;
newnode(rt,INF,0);newnode(c[rt][1],INF,rt);
pushup(c[rt][1]);pushup(rt);
F(i,1,n) a[i]=read();
build(key,1,n,c[rt][1]);
pushup(c[rt][1]);pushup(rt);
m=read();
F(i,1,m)
{
int x,y,z;
scanf("%s",ch);
if (ch[0]=='A'){x=read()+1;y=read()+1;z=read();solveadd(x,y,z);}
else if (ch[0]=='I'){x=read()+1;y=read();solveins(x,y);}
else if (ch[0]=='D'){x=read()+1;solvedel(x);}
else if (ch[0]=='M'){x=read()+1;y=read()+1;getmin(x,y);}
else if (ch[3]=='E'){x=read()+1;y=read()+1;solverev(x,y);}
else {x=read()+1;y=read()+1;z=read();revolve(x,y,z);}
}
}
}
