http://poj.org/problem?id=3580
神TM的SPLAY模板题
SPLAY的两种应用，一种维护集合，一种维护数列，这道作为维护数列的入门题不管怎么说也是要比文艺平衡树好的。
维护区间加，区间反转，插入元素，删除元素，区间最小值，REVOLVE操作只要把SPLAY分离之后再合并就行了，都是很基本的东西没什么好讲的，基本只要会线段树以及集合的SPLAY这个就很好写。
前提是你调得出来（括弧笑）
#include<cstdio>
using namespace std;
char s[8];
struct node{
int fa,r,l,s,num,add,min,re;
}t[200005];
int n,m,l,r,d,root;
void pushup(int k){
t[k].s=t[t[k].l].s+t[t[k].r].s+1;
t[k].min=t[k].num;
if(t[k].l>0)if(t[t[k].l].min<t[k].min)t[k].min=t[t[k].l].min;
if(t[k].r>0)if(t[t[k].r].min<t[k].min)t[k].min=t[t[k].r].min;
}
inline int read(){
int ret=0;
char c=getchar();
while((c>'9')||(c<'0'))c=getchar();
while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ret;
}
void pushdown(int k){
if(t[k].re){
int tmp=t[k].l;
t[k].l=t[k].r;
t[k].r=tmp;
if(t[k].l>0)t[t[k].l].re^=1;
if(t[k].r>0)t[t[k].r].re^=1;
t[k].re=false;
}
if(t[k].add==0)return;
if(t[k].l>0){t[t[k].l].add+=t[k].add;t[t[k].l].min+=t[k].add;t[t[k].l].num+=t[k].add;}
if(t[k].r>0){t[t[k].r].add+=t[k].add;t[t[k].r].min+=t[k].add;t[t[k].r].num+=t[k].add;}
t[k].add=0;
}
void rorate(int k,int i){
int tmp=t[k].fa;
t[k].fa=t[tmp].fa;
if(t[t[tmp].fa].l==tmp)t[t[tmp].fa].l=k;
else t[t[tmp].fa].r=k;
t[tmp].fa=k;
if(i==0){
if(t[k].l>0)t[t[k].l].fa=tmp;
t[tmp].r=t[k].l;
t[k].l=tmp;
}else{
if(t[k].r>0)t[t[k].r].fa=tmp;
t[tmp].l=t[k].r;
t[k].r=tmp;
}
pushup(tmp);pushup(k);
}
void splay(int k,int g){
pushdown(g);
while(t[k].fa!=g){
int tmp=t[k].fa;
if(t[tmp].fa==g){
pushdown(tmp);pushdown(k);
if(t[tmp].r==k)rorate(k,0);
else rorate(k,1);
}
else{
int Tmp=t[tmp].fa;
pushdown(Tmp);pushdown(tmp);pushdown(k);
if(t[Tmp].l==tmp){
if(t[tmp].l==k)rorate(tmp,1);
else rorate(k,0);
rorate(k,1);
}else{
if(t[tmp].r==k)rorate(tmp,0);
else rorate(k,1);
rorate(k,0);
}
}
}
if(g==0)root=k;
}
int find(int x,int roo){
int k=roo;
pushdown(k);
while((t[t[k].l].s+1!=x)){
if(t[t[k].l].s+1>x)k=t[k].l;
else x-=t[t[k].l].s+1,k=t[k].r;
pushdown(k);
}
return k;
}
void ins(int x,int y){
int k=find(x+1,root);
splay(k,0);
k=find(x,root);
splay(k,root);
n++;
t[k].r=n;
t[n].num=t[n].min=y;t[n].fa=k;t[n].s=1;t[n].add=0;
pushup(k);
pushup(root);
}
void del(int x){
int k=find(x-1,root);
splay(k,0);
k=find(x+1,root);
splay(k,root);
t[t[k].l].s=0;
t[k].l=0;
pushup(k);
pushup(root);
}
int findmin(int x,int y){
int k=find(x-1,root);
splay(k,0);
k=find(y+1,root);
splay(k,root);
return t[t[k].l].min;
}
void add(int x,int y,int d){
int k=find(x-1,root);
splay(k,0);
k=find(y+1,root);
splay(k,root);
t[t[k].l].add+=d;t[t[k].l].num+=d;t[t[k].l].min+=d;
}
void reve(int x,int y){
int k=find(x-1,root);
splay(k,0);
k=find(y+1,root);
splay(k,root);
t[t[k].l].re^=1;
}
void revo(int x,int y,int d){
int k=find(x-1,root);
splay(k,0);
k=find(y+1,root);
splay(k,root);
int tmp=find(d,t[k].l);
splay(tmp,k);
int Tmp=t[tmp].r;
pushdown(Tmp);
while(t[Tmp].r){
Tmp=t[Tmp].r;
pushdown(Tmp);
}
splay(Tmp,tmp);
pushdown(Tmp);
t[Tmp].r=tmp;t[Tmp].fa=k;
t[tmp].fa=Tmp;t[tmp].r=0;
t[k].l=Tmp;
pushup(tmp);
pushup(Tmp);
}
int main(){
n=read();
root=1;
t[1].fa=0;t[1].s=n+2;t[1].re=false;t[1].min=t[1].num=1000000000;
for(int i=2;i<=n+1;i++){
t[i].num=read();
t[i-1].r=i;
t[i].fa=i-1;t[i].s=n+3-i;t[i].re=false;
}
t[n+2].fa=n+1;t[n+1].r=n+2;t[n+2].s=1;t[n+2].re=false;t[n+2].num=t[n+2].min=1000000000;
for(int i=n+1;i>0;i--)if(t[i].num>t[i+1].min)t[i].min=t[i+1].min;
else t[i].min=t[i].num;
n+=2;
m=read();
for(int i=1;i<=m;i++){
scanf("%s",&s);
if(s[0]=='A'){
l=read();r=read();d=read();
add(l+1,r+1,d);
}else if(s[0]=='M'){
l=read();r=read();
printf("%d\n",findmin(l+1,r+1));
}else if(s[0]=='D'){
d=read();
del(d+1);
}else if(s[0]=='I'){
l=read();d=read();
ins(l+1,d);
}else if(s[3]=='E'){
l=read();r=read();
reve(l+1,r+1);
}else if(s[3]=='O'){
l=read();r=read();d=read();
d%=(r-l+1);
if(d==0)continue;
d=r-l+1-d;
revo(l+1,r+1,d);
}
}
}
评论 (0)
