今天是2018/4/23，DCDCBigBig的第三十五篇博文

由于本人太菜，滚回去复习平衡树了……

Splay

//Orz https://blog.csdn.net/clove_unique/article/details/50630280
//BZOJ3224 普通平衡树 各类平衡树模板题
//n个操作 
//1 x 表示插入x
//2 x 表示删除x（如果有多个相同的则只删除一个）
//3 x 表示查询x的排名 
//4 x 表示查询排名为x的数 
//5 x 表示查询x的前驱 
//6 x 表示查询x的后继 
#include
#include
#include
#include
using namespace std;
struct Splay{struct node{int v,fa,son[2],siz,sum;//0:左儿子 1:右儿子}t[200001];int tot,rt;Splay(){tot=rt=0;}void newnode(int val){t[++tot].v=val;t[tot].fa=t[tot].son[0]=t[tot].son[1]=0;t[tot].sum=t[tot].siz=1;}void clear(int x){t[x].v=t[x].fa=t[x].son[0]=t[x].son[1]=t[x].sum=t[x].siz=0;}int lr(int x){return t[t[x].fa].son[1]==x;}void update(int x){if(x){t[x].siz=t[x].sum;if(t[x].son[0])t[x].siz+=t[t[x].son[0]].siz;if(t[x].son[1])t[x].siz+=t[t[x].son[1]].siz;}}void rotate(int x){int p=t[x].fa,pp=t[p].fa,ch=lr(x);t[p].son[ch]=t[x].son[ch^1];t[t[p].son[ch]].fa=p;t[p].fa=x;t[x].son[ch^1]=p;t[x].fa=pp;if(pp)t[pp].son[t[pp].son[1]==p]=x;update(p);update(x);}void splay(int x,int p){for(int f;(f=t[x].fa)!=p;rotate(x)){if(t[f].fa!=p)rotate(lr(x)==lr(f)?f:x);}if(!p)rt=x;}void insert(int x){if(rt==0){newnode(x);rt=tot;return;}int now=rt,f=0;for(;;){if(t[now].v==x){t[now].sum++;update(now);update(f);splay(now,0);return;}f=now;now=t[now].son[t[now].vif(!now){newnode(x);t[tot].fa=f;t[f].son[t[f].v0);return;}}}int pre(){int now=t[rt].son[0];while(t[now].son[1])now=t[now].son[1];return now;}int nxt(){int now=t[rt].son[1];while(t[now].son[0])now=t[now].son[0];return now;}int find(int x){int ans=0,now=rt;for(;;){if(x0];else{ans+=(t[now].son[0]?t[t[now].son[0]].siz:0);if(x==t[now].v){splay(now,0);return ans+1;}ans+=t[now].sum;now=t[now].son[1];}}}int findx(int x){int now=rt;for(;;){if(t[now].son[0]&&x<=t[t[now].son[0]].siz)now=t[now].son[0];else{int tmp=(t[now].son[0]?t[t[now].son[0]].siz:0)+t[now].sum;if(x<=tmp)return t[now].v;x-=tmp;now=t[now].son[1];}}}void del(int x){int kk=find(x);if(t[rt].sum>1){t[rt].sum--;return;}if(!t[rt].son[0]&&!t[rt].son[1]){clear(rt);rt=0;return;}if(!t[rt].son[1]){int rrt=rt;rt=t[rrt].son[0];t[rt].fa=0;clear(rrt);return;}if(!t[rt].son[0]){int rrt=rt;rt=t[rrt].son[1];t[rt].fa=0;clear(rrt);return;}int pr=pre(),rrt=rt;splay(pr,0);t[t[rrt].son[1]].fa=rt;t[rt].son[1]=t[rrt].son[1];clear(rrt);update(rt);}int ppre(int x){insert(x);int ans=t[pre()].v;del(x);return ans;}int nnxt(int x){insert(x);int ans=t[nxt()].v;del(x);return ans;}
}splaytree;
int n,op,x;
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&op,&x);switch(op){case 1:splaytree.insert(x);break;case 2:splaytree.del(x);break;case 3:printf("%d\n",splaytree.find(x));break;case 4:printf("%d\n",splaytree.findx(x));break;case 5:printf("%d\n",splaytree.ppre(x));break;case 6:printf("%d\n",splaytree.nnxt(x));break;}} return 0;
}

Splay++

//BZOJ3223 文艺平衡树 区间反转
#include
#include
#include
#include
using namespace std;
struct node{int v,fa,son[2],siz;bool rev;
}t[1000001];
int n,m,l,r,rt;
int lr(int x){return t[t[x].fa].son[1]==x;
}
void update(int x){t[x].siz=t[t[x].son[0]].siz+t[t[x].son[1]].siz+1;
}
void pd(int x){if(t[x].rev){t[x].rev=0;t[t[x].son[0]].rev^=1;t[t[x].son[1]].rev^=1;swap(t[x].son[0],t[x].son[1]);}
}
void rotate(int &u,int x){int p=t[x].fa,pp=t[p].fa,ch=lr(x);pd(p);if(p==u)u=x;else t[pp].son[lr(p)]=x;t[x].fa=pp;t[p].son[ch]=t[x].son[ch^1];t[t[p].son[ch]].fa=p;t[x].son[ch^1]=p;t[p].fa=x;update(p);update(x);
}
void splay(int &u,int x){pd(x);while(x!=u){int p=t[x].fa;if(p!=u){rotate(u,lr(x)==lr(p)?p:x);}rotate(u,x);}
}
int find(int u,int x){if(!u)return 0;pd(u);if(x<=t[t[u].son[0]].siz)return find(t[u].son[0],x);if(x==t[t[u].son[0]].siz+1)return u;return find(t[u].son[1],x-t[t[u].son[0]].siz-1);
}
void rever(int l,int r){splay(rt,find(rt,l));splay(t[rt].son[1],find(rt,r+2));t[t[t[rt].son[1]].son[0]].rev^=1;
}
void write(int x){if(!x)return;pd(x);write(t[x].son[0]);if(x>1&&x2)printf("%d ",x-1);write(t[x].son[1]);
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n+2;i++){t[i].v=i;t[i].siz=n-i+3;t[i].fa=i-1;t[i].son[1]=i+1;t[i].son[0]=t[i].siz=0;}t[n+2].son[1]=0;rt=1;for(int i=1;i<=m;i++){scanf("%d%d",&l,&r);rever(l,r);}write(rt);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！