题目链接:http://poj/problem?id=3580
题意:一个数列,6种操作:
(1)将[L,R]之间的数字都加d;
(2)将[L,R]之间的数字翻转;
(3)将[L,R]之间的数字向右循环d次;
(4)在pos位置插入数字d;
(5)删掉pos位置的数字;
(6)输出[L,R]的最小值。
思路:第一第二种操作在节点上增加标记;第三种操作等价于将[A,B],[B+1,C]两个区间的数字交换。首先将A-1和C+1调整到根节点和根节点的右子树,则[A,C]区间就在根节点右子树的左子树上。接着将B调整到根节点右子树的左子树P,则[A,B-1]在P的左子树L,[B+1,C]在P的右子树R,最后将R截下放在L的左子树。第四将pos调整到根节点,将pos+1调整到根节点的右子树,则插入位置为根节点右子树的左子树;删除时将pos调整到根节点,pos+2调整到根节点右子树,则pos到了根节点右子树的左子树直接删掉即可;最小值在节点上增加一个记录即可。
struct node
{
int Min,value,rev,lazy,size;
node* c[2];
node* p;
};
node a[N],*root,*null;
int n,m,b[N],cnt;
node* newNode(int value,node *p)
{
node *e=a+(cnt++);
e->value=value;
e->size=1;
e->p=p;
e->Min=value;
e->lazy=e->rev=0;
e->c[0]=e->c[1]=null;
return e;
}
void pushDown(node *p)
{
if(p==null) return;
if(p->rev)
{
p->rev=0;
swap(p->c[0],p->c[1]);
p->c[0]->rev^=1;
p->c[1]->rev^=1;
}
if(p->lazy)
{
p->value+=p->lazy;
p->Min+=p->lazy;
p->c[0]->lazy+=p->lazy;
p->c[1]->lazy+=p->lazy;
p->lazy=0;
}
}
void pushUp(node *p)
{
if(p==null) return;
p->size=p->c[0]->size+p->c[1]->size+1;
p->Min=min(p->value,min(p->c[0]->Min,p->c[1]->Min));
}
void init()
{
cnt=0;
null=0;
null=newNode(INF,0);
null->size=0;
root=newNode(INF,null);
root->c[1]=newNode(INF,root);
pushUp(root);
}
void rotate(node *x,int k)
{
node *y=x->p;
pushDown(x->c[0]);
pushDown(x->c[1]);
pushDown(y->c[!k]);
y->c[k]=x->c[!k];
y->c[k]->p=y;
x->p=y->p;
if(y->p->c[0]==y) y->p->c[0]=x;
else y->p->c[1]=x;
y->p=x;
x->c[!k]=y;
pushUp(y);
pushUp(x);
if(root==y) root=x;
}
void splay(node *x,node *y)
{
pushDown(x);
while(x->p!=y)
{
if(x->p->p==y)
{
if(x->p->c[0]==x) rotate(x,0);
else rotate(x,1);
}
else if(x->p->p->c[0]==x->p)
{
if(x->p->c[0]==x) rotate(x->p,0);
else rotate(x,1);
rotate(x,0);
}
else
{
if(x->p->c[1]==x) rotate(x->p,1);
else rotate(x,0);
rotate(x,1);
}
}
}
void select(int k,node *y)
{
node *x=root;
pushDown(x);
while(k!=x->c[0]->size+1)
{
if(k<x->c[0]->size+1) x=x->c[0];
else
{
k-=x->c[0]->size+1;
x=x->c[1];
}
pushDown(x);
}
splay(x,y);
}
void build(int L,int R,int b[],node *p,int side)
{
if(L>R) return;
int mid=(L+R)>>1;
node *x=newNode(b[mid],p);
p->c[side]=x;
build(L,mid-1,b,x,0);
build(mid+1,R,b,x,1);
pushUp(x);
}
void insert(int pos,int cnt,int b[])
{
select(pos+1,null);
select(pos+2,root);
build(1,cnt,b,root->c[1],0);
splay(root->c[1]->c[0],null);
}
void add(int pos,int cnt,int det)
{
select(pos,null);
select(pos+cnt+1,root);
root->c[1]->c[0]->lazy+=det;
splay(root->c[1]->c[0],null);
}
void del(int pos,int cnt)
{
select(pos,null);
select(pos+cnt+1,root);
root->c[1]->c[0]=null;
splay(root->c[1],null);
}
void reverse(int pos,int cnt)
{
select(pos,null);
select(pos+cnt+1,root);
root->c[1]->c[0]->rev^=1;
splay(root->c[1]->c[0],null);
}
void revolve(int L,int R,int k)
{
int len=R-L+1,A,B,C;
k%=len;
if(!k) return;
A=L+1;B=R-k+1;C=R+1;
node *p1,*p2,*p3,*p4;
select(A-1,null); p1=root;
select(C+1,null); p2=root;
select(A,null); p3=root;
select(B,null); p4=root;
select(A-1,null);
select(C+1,p1);
select(B,p2);
p3->c[0]=p4->c[1];
p4->c[1]=null;
splay(p3,null);
}
int getMin(int pos,int cnt)
{
select(pos,null);
select(pos+cnt+1,root);
return root->c[1]->c[0]->Min;
}
int main()
{
init();
scanf("%d",&n);
int i,x,y,z;
char op[15];
for(i=1;i<=n;i++) scanf("%d",b+i);
insert(0,n,b);
scanf("%d",&m);
while(m--)
{
scanf("%s",op);
if(op[0]=='A')
{
scanf("%d%d%d",&x,&y,&z);
add(x,y-x+1,z);
}
else if(op[0]=='R'&&op[3]=='E')
{
scanf("%d%d",&x,&y);
reverse(x,y-x+1);
}
else if(op[0]=='R'&&op[3]=='O')
{
scanf("%d%d%d",&x,&y,&z);
revolve(x,y,z);
}
else if(op[0]=='I')
{
scanf("%d%d",&x,&b[1]);
insert(x,1,b);
}
else if(op[0]=='D')
{
scanf("%d",&x);
del(x,1);
}
else
{
scanf("%d%d",&x,&y);
printf("%d\n",getMin(x,y-x+1));
}
}
return 0;
}
更多推荐
POJ 3580 SuperMemo(splay)
发布评论