POJ 3580 点击打开链接
#include <cstdio>
#include <algorithm>
const int inf=0x3f3f3f3f;
const int N=200100;
using namespace std;
//除了Get_pre和Get_nxt函数,其他节点都是按照下标从小到大排列的
struct node
{
node *ch[2],*fa;
int sz,val,mn,add,rev;
void Pushup()
{
sz=1;
mn=val;
if(ch[0]) sz+=ch[0]->sz,mn=min(mn,ch[0]->mn);
if(ch[1]) sz+=ch[1]->sz,mn=min(mn,ch[1]->mn);
}
void Pushdown()
{
if(rev)
{
rev^=1;
swap(ch[0],ch[1]);
if(ch[0]) ch[0]->rev^=1;
if(ch[1]) ch[1]->rev^=1;
}
if(add)
{
if(ch[0]) ch[0]->add+=add,ch[0]->val+=add,ch[0]->mn+=add;
if(ch[1]) ch[1]->add+=add,ch[1]->val+=add,ch[1]->mn+=add;
add=0;
}
}
};
node nodes[N];
node *root;
int node_cnt;
int n,m,l,r,val,a[N];
char op[10];
node* Newnode(node *&p,node *fa,int val)
{
p=&nodes[node_cnt++];
p->fa=fa;
p->val=val;
p->mn=val;
p->add=0;
p->rev=0;
p->ch[0]=p->ch[1]=NULL;
p->sz=1;
return p;
}
int Get(node *t)
{
return t->fa->ch[1]==t;
}
void Rotate(node *t)
{
int k=Get(t)^1;
t->Pushdown();
node *a=t->ch[k],*y=t->fa,*z=y->fa;
if(z) z->ch[Get(y)]=t;
t->ch[k]=y;
y->ch[k^1]=a;
if(a) a->fa=y;
y->fa=t;
t->fa=z;
y->Pushup();
t->Pushup();
}
void Splay(node *t,node *f)
{
for(;t->fa!=f;Rotate(t))
if(t->fa->fa!=f) Rotate(Get(t)==Get(t->fa)?t->fa:t);
if(f==NULL) root=t;
}
node* Select(node *t,int k)//选择第k大的节点
{
while(1)
{
t->Pushdown();
int cnt=t->ch[0]?t->ch[0]->sz+1:1;
if(k==cnt) return t;
if(k>cnt) k-=cnt,t=t->ch[1];
else t=t->ch[0];
}
}
void Build(int l,int r,node *&t,node *fa)
{
if(l>r) return;
int m=l+r>>1;
Newnode(t,fa,a[m]);
Build(l,m-1,t->ch[0],t);
Build(m+1,r,t->ch[1],t);
t->Pushup();
}
void Init()
{
node_cnt=0,root=NULL;
Newnode(root,NULL,inf);
Newnode(root->ch[1],root,inf);
root->sz=2;
Build(1,n,root->ch[1]->ch[0],root->ch[1]);
root->ch[1]->Pushup();
root->Pushup();
}
node* Get_pre(node *t,int k)//按val排序,得出最接近k且val<=k的val值的前驱节点
{
if(t==NULL) return NULL;
if(t->val>k) return Get_pre(t->ch[0],k);
node *tmp=Get_pre(t->ch[1],k);
return tmp?tmp:t;
}
node* Get_nxt(node *t,int k)//按val排序,得出最接近k且val>=k的val值的后驱节点
{
if(t==NULL) return NULL;
if(t->val<k) return Get_nxt(t->ch[1],k);
node *tmp=Get_nxt(t->ch[0],k);
return tmp?tmp:t;
}
void Add(int l,int r,int val)//[l,r]区间每个节点的val值内加val
{
node *x=Select(root,l-1),*y=Select(root,r+1);
Splay(x,NULL),Splay(y,x);
y->ch[0]->mn+=val;
y->ch[0]->add+=val;
y->ch[0]->val+=val;
y->Pushup();
x->Pushup();
}
void Reverse(int l,int r)//[l,r]区间的节点翻转
{
node *x=Select(root,l-1),*y=Select(root,r+1);
Splay(x,NULL),Splay(y,x);
y->ch[0]->rev^=1;
}
void Revolve(int l,int r,int T)//将[l,r]区间的节点向右循环推动T次,每次推一位
{
T%=r-l+1;
if(T==0) return;
node *x=Select(root,r-T),*y=Select(root,r+1);
Splay(x,NULL),Splay(y,x);
node *tmp=y->ch[0];
y->ch[0]=NULL;
y->Pushup();
x->Pushup();
x=Select(root,l-1),y=Select(root,l);
Splay(x,NULL),Splay(y,x);
y->ch[0]=tmp;
tmp->fa=y;
y->Pushup();
x->Pushup();
}
void Insert(int pos,int val)//在下标pos后插入一个节点
{
node *x=Select(root,pos),*y=Select(root,pos+1);
Splay(x,NULL),Splay(y,x);
Newnode(y->ch[0],y,val);
y->Pushup();
x->Pushup();
}
void Delete(int pos)//删除下标pos的节点
{
node *x=Select(root,pos-1),*y=Select(root,pos+1);
Splay(x,NULL),Splay(y,x);
y->ch[0]=NULL;
y->Pushup();
x->Pushup();
}
/*
void Delete(node *t)//删除节点t
{
Splay(t,NULL);
int pos=t->ch[0]?t->ch[0]->sz+1:1;
node *x=Select(root,pos-1),*y=Select(root,pos+1);
Splay(x,NULL),Splay(y,x);
y->ch[0]=NULL;
y->Pushup();
x->Pushup();
}
*/
int Min(int l,int r)//[l,r]区间内最小的val
{
node *x=Select(root,l-1),*y=Select(root,r+1);
Splay(x,NULL),Splay(y,x);
return y->ch[0]->mn;
}
void Print(node *t)
{
if(t->ch[0]) Print(t->ch[0]);
printf("val:%d\n",t->val);
if(t->ch[1]) Print(t->ch[1]);
}
int main()
{
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
Init();
scanf("%d",&m);
while(m--)
{
scanf("%s",op);
if(op[0]=='A') scanf("%d%d%d",&l,&r,&val),Add(++l,++r,val);//因为最左端插入了一个点,所以所有区间都要+1
else if(op[0]=='M') scanf("%d%d",&l,&r),printf("%d\n",Min(++l,++r));
else if(op[0]=='I') scanf("%d%d",&l,&val),Insert(++l,val);
else if(op[0]=='D') scanf("%d",&l),Delete(++l);
else if(op[3]=='E') scanf("%d%d",&l,&r),Reverse(++l,++r);
else scanf("%d%d%d",&l,&r,&val),Revolve(++l,++r,val);
}
}
}
更多推荐
Splay模板
发布评论