POJ - 3580 SuperMemo
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
/*
给出一个数字序列,有6种操作:
(1) ADD x y d: 第x个数到第y个数加d 。
(2) REVERSE x y : 将区间[x,y]中的数翻转 。
(3) REVOLVE x y t :将区间[x,y]旋转t次,如1 2 3 4 5 旋转2次后就变成4 5 1 2 3 。
(4) INSERT x p :在第x个数后面插入p 。
(5) DELETE x :删除第x个数 。
(6) MIN x y : 查询区间[x,y]中的最小值 。
*/
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=2e5+500;
const int INF=1e9;
int tot,root,n,m;
int ch[maxn][2]; //左右子节点的节点编号
int f[maxn]; //该节点父亲节点编号
int sz[maxn]; //以该节点为根的包括子树的节点数
int val[maxn]; //该节点的值
int lazy[maxn]; //该节点的lazy值(要加的)
int rev[maxn]; //该节点是否要反转(0||1)
int mi[maxn]; //以该节点为根节点中所有子节点包括自己的最小值
void pushup(int rt)
{
if(!rt) return;
sz[rt]=1,mi[rt]=val[rt]; //只有根节点才pushup
if(ch[rt][0]) sz[rt]=sz[ch[rt][0]]+sz[rt],mi[rt]=min(mi[rt],mi[ch[rt][0]]); //更新节点个数和最小值
if(ch[rt][1]) sz[rt]=sz[ch[rt][1]]+sz[rt],mi[rt]=min(mi[rt],mi[ch[rt][1]]);
}
void update_add(int rt,int k)
{
if(rt) //lazy标记更新
{
val[rt]+=k;
mi[rt]+=k;
lazy[rt]+=k;
}
}
void update_rev(int rt)
{
if(rt) //rev标记更新
{
swap(ch[rt][0],ch[rt][1]);
rev[rt]=rev[rt]^1; //反转过就不用再反转了
}
}
void pushdown(int rt)
{
if(!rt) return;
if(lazy[rt])
{
update_add(ch[rt][0],lazy[rt]);
update_add(ch[rt][1],lazy[rt]);
lazy[rt]=0;
}
if(rev[rt])
{
update_rev(ch[rt][0]);
update_rev(ch[rt][1]);
rev[rt]=0;
}
}
int kth(int x,int k) //返回以x节点为根节点的第k个数的节点编号
{
pushdown(x);
if(sz[ch[x][0]]+1==k) return x;
else if(sz[ch[x][0]]>=k) return kth(ch[x][0],k);
else return kth(ch[x][1],k-sz[ch[x][0]]-1);
}
void newnode(int rt,int k,int fa)
{
ch[rt][0]=ch[rt][1]=0;
f[rt]=fa,sz[rt]=1;
val[rt]=mi[rt]=k;
lazy[rt]=rev[rt]=0;
}
void delnode(int rt)
{
val[rt]=ch[rt][0]=ch[rt][1]=sz[rt]=mi[rt]=f[rt]=lazy[rt]=rev[rt]=0;
}
void Rotate(int x,int p) //p==0 左旋 p==1 右旋
{
int y=f[x],z=f[y];
pushdown(z),pushdown(y),pushdown(x);
ch[y][!p]=ch[x][p],f[ch[x][p]]=y;
ch[z][ch[z][1]==y]=x,f[x]=z;
ch[x][p]=y,f[y]=x;
pushup(y),pushup(z);
}
void splay(int x,int goal) //将x节点转为goal的子节点
{
while(f[x]!=goal) //没有转到所要求的就不停止
{
int y=f[x],z=f[y];
pushdown(z),pushdown(y),pushdown(x);
if(f[y]==goal) Rotate(x,ch[y][0]==x); //如果只要再旋转一次
else
{
int p=(ch[z][0]==y);
if(ch[y][!p]==x) //zig-zig zag-zag
{
Rotate(y,p);
Rotate(x,p);
}
else //zig-zag zag-zig
{
Rotate(x,!p);
Rotate(x,p);
}
}
}
if(goal==0) root=x; //根节点改变
}
void build(int &rt,int l,int r,int fa)
{
if(l>r) return;
int mid=(l+r)/2;
rt=mid;
newnode(rt,val[rt],fa);
build(ch[rt][0],l,mid-1,rt);
build(ch[rt][1],mid+1,r,rt);
pushup(rt); //根节点需要更新
}
void init(int n)
{
ch[0][0]=ch[0][1]=f[0]=sz[0]=lazy[0]=rev[0]=mi[0]=0;
build(root,1,n,0);
}
void add(int l,int r,int k)
{
int x=kth(root,l-1),y=kth(root,r+1);
splay(x,0),splay(y,x);
update_add(ch[y][0],k);
}
void Insert(int l,int k)
{
int x=kth(root,l),y=kth(root,l+1);
splay(x,0),splay(y,x);
newnode(++tot,k,y);
ch[y][0]=tot;
pushdown(x),pushdown(y);
pushup(x);
splay(y,0);
}
int get_min(int l,int r)
{
int x=kth(root,l-1),y=kth(root,r+1);
splay(x,0),splay(y,x);
return mi[ch[y][0]];
}
void Delete(int k)
{
int x=kth(root,k-1),y=kth(root,k+1);
splay(x,0),splay(y,x);
delnode(ch[y][0]);
ch[y][0]=0;
sz[y]--;
}
void Reverse(int l,int r)
{
int x=kth(root,l-1),y=kth(root,r+1);
splay(x,0),splay(y,x);
update_rev(ch[y][0]);
}
void Revolve(int l1,int r1,int l2,int r2)
{
int x=kth(root,l2-1),y=kth(root,r2+1);
splay(x,0),splay(y,x);
int tmp_right=ch[y][0];
ch[y][0]=0;
x=kth(root,l1-1),y=kth(root,l1);
splay(x,0),splay(y,x);
ch[y][0]=tmp_right;
f[tmp_right]=y;
}
int main()
{
scanf("%d",&n);
val[1]=val[n+2]=INF;
for(int i=2;i<=n+1;i++) scanf("%d",&val[i]);
tot=n+2;
init(n+2);
scanf("%d",&m);
char s[10];
for(int i=1;i<=m;i++)
{
scanf("%s",s);
int l,r,d;
if(s[0]=='A')
{
scanf("%d%d%d",&l,&r,&d);
add(l+1,r+1,d);
}
else if(s[0]=='D')
{
scanf("%d",&d);
Delete(d+1);
}
else if(s[0]=='I')
{
scanf("%d%d",&l,&d);
Insert(l+1,d);
}
else if(s[0]=='M')
{
scanf("%d%d",&l,&r);
printf("%d\n",get_min(l+1,r+1));
}
else if(s[3]=='E')
{
scanf("%d%d",&l,&r);
Reverse(l+1,r+1);
}
else
{
scanf("%d%d%d",&l,&r,&d);
d=d%(r-l+1);
l++,r++;
Revolve(l,r-d,r-d+1,r);
}
}
return 0;
}
更多推荐
【Splay 超全模板!!】POJ - 3580 SuperMemo
发布评论