伸展树
多值版
#include<bits/stdc++.h>
using namespace std;
template<class T> inline bool read(T &x){
x=0;register char c=getchar();register bool f=0;
while(!isdigit(c)){if(c==EOF)return false;f^=c=='-',c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=-x;
return true;
}
template<class T>inline void print(T x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar('0'+x%10);
}
typedef long long ll;
const ll MAXN=1e5+8,inf=0x3f3f3f3f,mod=1e9+7;
struct Node {
int val,num,son_num;
int fa,lson,rson;
Node() {val=num=son_num=fa=rson=lson=0;}
Node(int f,int ls,int rs,int v,int n,int sn):
fa(f),lson(ls),rson(rs),val(v),num(n),son_num(sn) {}
}tree[MAXN];
int root,cnt;
inline void init(){root=cnt=0;}
inline bool islson(int x){return tree[tree[x].fa].lson==x?1:0;}
inline void update(int x){
if(!x)return;
tree[x].son_num=tree[x].num;
if(tree[x].lson)tree[x].son_num+=tree[tree[x].lson].son_num;
if(tree[x].rson)tree[x].son_num+=tree[tree[x].rson].son_num;
}
inline void rotate(int x){//默认x有父节点
int f=tree[x].fa,ff=tree[f].fa;//ff可能是0
if(islson(x)){//zig 右旋
tree[f].lson=tree[x].rson,tree[tree[x].rson].fa=f;
tree[x].rson=f,tree[f].fa=x;
}else{//zag 左旋
tree[f].rson=tree[x].lson,tree[tree[x].lson].fa=f;
tree[x].lson=f,tree[f].fa=x;
}
tree[x].fa=ff;
//必须这样判断，不能用islson，因为f的父节点已经是x了
if(tree[ff].lson==f)tree[ff].lson=x;
else tree[ff].rson=x;
update(f);//只需更新深度更大的f，x之后更新
}
inline void splay(int x,int end_pos) {
int f=tree[x].fa;
while(f^end_pos) {
if(tree[f].fa^end_pos) {//如果f不是根
if(islson(x)^islson(f))rotate(x);//zig+zag or zag+zig
else rotate(f);//zig+zig or zag+zag
}rotate(x);
f=tree[x].fa;
}
update(x);//最上层节点还没更新
root=x;
}
void insert(int v){
if(!root){//如果有节点。
tree[++cnt]=Node(0,0,0,v,1,1);
root=cnt;
return;
}
int now=root,f=0;
while(1){
if(tree[now].val==v){//原来有val节点
tree[now].num++;
tree[now].son_num++;
splay(now,0);
break;
}
f=now;
if(v<tree[now].val)now=tree[now].lson;
else now=tree[now].rson;
if(now==0){//创建节点
tree[++cnt]=Node(f,0,0,v,1,1);//父节点是f
if(v>tree[f].val)tree[f].rson=cnt;
else tree[f].lson=cnt;
splay(cnt,0);
break;
}
}
}
inline int pre(){//返回根节点的val值的前继的节点编号
int now=tree[root].lson;
while(tree[now].rson)now=tree[now].rson;
return now;
}
inline int nxt(){//后继
int now=tree[root].rson;
while(tree[now].lson)now=tree[now].lson;
return now;
}
int find_val_rank(int val){//返回值为val的最小的排名
int now=root,ans=0;
while(1){
//如果当前节点值大于val，进入左子树
if(val<tree[now].val)now=tree[now].lson;
else{//否则，进入右子树
//加上值绝对小于val的数量
if(tree[now].lson)ans+=tree[tree[now].lson].son_num;
if(tree[now].val==val){
splay(now,0);
return ans+1;
}
//否则，当前节点值小于val，加上
ans+=tree[now].num;
now=tree[now].rson;
}
}
}
/*
将要删除的节点旋转到root
考虑删除root
1. 如果root有多余1次出现，直接num--
2. 如果左右子树都为空，变成空树
3. 只有一个儿子
4. 有两个儿子
*/
inline void del(int val){/
find_val_rank(val);
if(tree[root].num>1){//如果大于一个，直接减少一个。
tree[root].num--;
tree[root].son_num--;
return;
}
if(!tree[root].lson&&!tree[root].rson){//如果左右子树都为空，则树为空
root=cnt=0;
return;
}
if(!tree[root].lson){//如果没有左儿子，直接将右儿子作为根
root=tree[root].rson;
tree[root].fa=0;
return;
}
if(!tree[root].rson){//如果没有右儿子，将左儿子作为根
root=tree[root].lson;
tree[root].fa=0;
return;
}
//左右儿子都存在，寻找前继，把它设为根
//这样的话，原来的根就没有左子树了
//未开始操作前，新的root的右儿子就是原来的根
int old_root=root,pre_node=pre();
splay(pre_node,0);
tree[root].rson=tree[old_root].rson;
tree[tree[old_root].rson].fa=root;
update(root);
}
//返回第kth名的值
int find_kth_rank(int kth){
int now=root;
while(1){
//如果now有左儿子且左儿子里节点数大于kth，答案肯定在左儿子
if(tree[now].lson&&kth<=tree[tree[now].lson].son_num)
now=tree[now].lson;
else{//在右儿子或now
int ls=tree[now].lson,sum=tree[now].num;
if(ls)sum+=tree[ls].son_num;//有左儿子，sum加上左儿子里的数量
if(kth<=sum)return tree[now].val;
//只有左儿子kth>sum，加上now就符合，所以正确。
kth-=sum;//减去左儿子和now节点的的数量，进入右儿子
now=tree[now].rson;
}
}
}
int main() {
int n,op,x;
read(n);
while(n--){
read(op),read(x);
if(op==1)insert(x);
else if(op==2)del(x);
else if(op==3)printf("%d
",find_val_rank(x));
else if(op==4)printf("%d
",find_kth_rank(x));
else if(op==5){
insert(x);//查询的时候先添加，这样就必定有x节点，就能求出x的前继了
printf("%d
",tree[pre()].val);
del(x);
}else{
insert(x);
printf("%d
",tree[nxt()].val);
del(x);
}
}
return 0;
}
单值版
struct Splay{
int val[MAXN],num[MAXN],ls[MAXN],rs[MAXN],fa[MAXN];
inline void up(int x){//因为所有节点代表一个值，所以最初是1
num[x]=1;
if(ls[x])num[x]+=num[ls[x]];
if(rs[x])num[x]+=num[rs[x]];
}
int cnt,root;
inline int build(int l,int r,int f){
//建树，[l,mid-1],mid,[mid+1,r],保证中序遍历是原序列
int mid=(l+r)>>1;
int id=++cnt;//用另一个变量存储cnt，递归先改变cnt，再return
num[id]=1,fa[id]=f;
scanf("%d",val+id);
if(l==r){ls[id]=rs[cnt]=0;return id;}
if(l<mid)ls[id]=build(l,mid-1,id);
if(r>mid)rs[id]=build(mid+1,r,id);
return up(id),id;
}
inline bool islson(int x){return ls[fa[x]]==x?1:0;}
inline void rotate(int x){//单旋
int f=fa[x],ff=fa[f];
if(islson(x)){//zig
ls[f]=rs[x],fa[rs[x]]=f;
rs[x]=f,fa[f]=x;
}else{//zag
rs[f]=ls[x],fa[ls[x]]=f;
ls[x]=f,fa[f]=x;
}
fa[x]=ff;
if(ls[ff]==f)ls[ff]=x;
else rs[ff]=x;
up(f);//只要更新x下方节点
}
void splay(int x,int pos){//伸展为pos的子节点
int f=fa[x],ff=fa[f];
while(f^pos){
if(ff^pos){//如果ff就是pos,只需要再旋转一次即可。
if(islson(x)^islson(f))rotate(x);
else rotate(f);
}
rotate(x),f=fa[x],ff=fa[f];
}up(x);
if(!pos)root=x;//pos可能不为零
}
void insert(int vv){
cnt++;
if(!root){
val[cnt]=vv,num[cnt]=1,root=cnt;
return;
}
int x=root,f;
while(x){
f=x;
if(vv<val[x])x=ls[x];
else x=rs[x];
}
fa[cnt]=f,val[cnt]=vv,num[cnt]=1;
if(vv>val[f])rs[f]=cnt;
else ls[f]=cnt;
splay(cnt,0);
}
inline int find_kth(int k){//返回第k个节点编号
int x=root;
while(1){
if(ls[x]&&k<=num[ls[x]])x=ls[x];
else{
int sum=1;//每个节点都是唯一值，不会重复出现。
if(ls[x])sum+=num[ls[x]];
if(k<=sum)return splay(x,0),x;
//一定要splay，不然单调数据卡爆
k-=sum;
x=rs[x];
}
}
}
}
伸展树（区间旋转）
交换节点下面的所有左右儿子，则中序遍历结果和原序列相反，即旋转。
思路：要旋转的区间为[l,r]，将l-1代表的点旋转到root，再将r+1代表的点旋转到root的右儿子处，则：
x代表的是区间内的点 <=> x在r+1代表的点的左子树里面
//a序列m次翻转
#include<bits/stdc++.h>
using namespace std;
template<class T> inline bool read(T &x){
x=0;register char c=getchar();register bool f=0;
while(!isdigit(c)){if(c==EOF)return false;f^=c=='-',c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=-x;
return true;
}
template<class T>inline void print(T x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar('0'+x%10);
}
typedef long long ll;
const ll MAXN=1e5+8,inf=0x3f3f3f3f,mod=1e9+7;
int v[MAXN],num[MAXN],ls[MAXN],rs[MAXN],fa[MAXN];
int a[MAXN],n,m,cnt,root;
bool flag[MAXN];
inline void up(int x){//因为所有节点代表一个值，所以最初是1
num[x]=1;
if(ls[x])num[x]+=num[ls[x]];
if(rs[x])num[x]+=num[rs[x]];
}
inline void down(int x){//下放标记
swap(ls[x],rs[x]);
flag[ls[x]]^=1;
flag[rs[x]]^=1;
flag[x]=0;
}
inline bool islson(int x){return ls[fa[x]]==x?1:0;}
inline int build(int l,int r,int f){
//建树，[l,mid-1],mid,[mid+1,r],保证中序遍历是原序列
int mid=(l+r)>>1;
int id=++cnt;//用另一个变量存储cnt，因为递归先改变cnt，再return
num[id]=1;
fa[id]=f;
v[id]=a[mid];
if(l==r){ls[id]=rs[cnt]=0;return id;}
if(l<mid)ls[id]=build(l,mid-1,id);
if(r>mid)rs[id]=build(mid+1,r,id);
up(id);
return id;
}
inline void rotate(int x){//单旋
int f=fa[x],ff=fa[f];
if(islson(x)){//zig
ls[f]=rs[x],fa[rs[x]]=f;
rs[x]=f,fa[f]=x;
}else{//zag
rs[f]=ls[x],fa[ls[x]]=f;
ls[x]=f,fa[f]=x;
}
fa[x]=ff;
if(ls[ff]==f)ls[ff]=x;
else rs[ff]=x;
up(f);//值更新x下方节点
}
inline void splay(int x,int end_pos){
int f=fa[x],ff=fa[f];
while(f^end_pos){
if(flag[f])down(f);//因为要改变f和x的位置，所以要先putdown
if(flag[x])down(x);
if(ff^end_pos){//这里和其他不同，如果ff就是end_pos,只需要再旋转一次即可。
if(islson(x)^islson(f))rotate(x);
else rotate(f);
}
rotate(x);
f=fa[x];ff=fa[f];
}
up(x);
if(!end_pos)root=x;//end_pos可能不为零
}
inline int find_kth(int k){//返回第k个节点编号
int x=root;
while(1){
if(flag[x])down(x);
if(ls[x]&&k<=num[ls[x]])x=ls[x];
else{
int sum=1;//每个节点都是唯一值，不会重复出现。
if(ls[x])sum+=num[ls[x]];
if(k<=sum)return x;
k-=sum;
x=rs[x];
}
}
}
inline void change(int x,int y){
int l=find_kth(x-1),r=find_kth(y+1);
//把第x-1个节点旋转至root
splay(l,0);
splay(r,root);//第y+1个节点旋转至root右儿子的左儿子
flag[ls[rs[root]]]^=1;
}
void get_ans(int x){//中序遍历
if(flag[x])down(x);
if(ls[x])get_ans(ls[x]);
a[++cnt]=v[x];
if(rs[x])get_ans(rs[x]);
}
int main() {
read(n),read(m);
for(int i=1;i<=n+2;++i)a[i]=i-1;
root=build(1,n+2,0);
int x,y;
while(m--){
read(x),read(y);
change(x+1,y+1);
}
cnt=0;//下面重新用到了cnt
get_ans(root);
for(int i=2;i<=n+1;++i)printf("%d ",a[i]);
return 0;
}
POJ-3481
#include<iostream>
using namespace std;
template<class T> inline bool read(T &x){
x=0;register char c=getchar();register bool f=0;
while(!isdigit(c)){if(c==EOF)return false;f^=c=='-',c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=-x;
return true;
}
template<class T>inline void print(T x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar('0'+x%10);
}
typedef long long ll;
const ll MAXN=1e6+8,inf=0x3f3f3f3f,mod=1e9+7;
int v[MAXN],num[MAXN],ls[MAXN],rs[MAXN],fa[MAXN],cnt,root;
int id[MAXN];
inline bool islson(int x){return ls[fa[x]]==x?1:0;}
inline void update(int x){
num[x]=1;
if(ls[x])num[x]+=num[ls[x]];
if(rs[x])num[x]+=num[rs[x]];
}
inline void rotate(int x){
int f=fa[x],ff=fa[f];
if(islson(x)){
ls[f]=rs[x],fa[rs[x]]=f;
rs[x]=f,fa[f]=x;
}else{
rs[f]=ls[x],fa[ls[x]]=f;
ls[x]=f,fa[f]=x;
}
fa[x]=ff;
if(ls[ff]==f)ls[ff]=x;
else rs[ff]=x;
update(f);
}
inline void splay(int x,int end_pos){
int f=fa[x];
while(f^end_pos){
if(fa[f]){
if(islson(x)^islson(f))rotate(x);
else rotate(f);
}
rotate(x);
f=fa[x];
}
update(x);
if(!end_pos)root=x;
}
inline void insert(int val,int i){
if(!root){
num[++cnt]=1;v[cnt]=val;id[cnt]=i;
root=cnt;fa[cnt]=0;
return;
}
int x=root;
while(1){
if(val<v[x]){
if(ls[x])x=ls[x];
else{
num[++cnt]=1;v[cnt]=val;id[cnt]=i;
fa[cnt]=x;ls[x]=cnt;
splay(cnt,0);
return;
}
}
else{
if(rs[x])x=rs[x];
else{
num[++cnt]=1;v[cnt]=val;id[cnt]=i;
fa[cnt]=x;rs[x]=cnt;
splay(cnt,0);
return;
}
}
}
}
inline int get_high(){
if(!root)return 0;
int x=root;
while(1){
if(rs[x])x=rs[x];
else return x;
}
}
inline int get_low(){
if(!root)return 0;
int x=root;
while(1){
if(ls[x])x=ls[x];
else return x;
}
}
inline int get_h_del(){
int res_pos=get_high();
splay(res_pos,0);
root=ls[res_pos];
fa[root]=0;
return id[res_pos];
}
inline int get_l_del(){
int res_pos=get_low();
splay(res_pos,0);
root=rs[res_pos];
fa[root]=0;
return id[res_pos];
}
int main() {
int op,k,p,res;
while(read(op)&&op){
if(op==1){
read(k),read(p);
insert(p,k);
}
else if(op==2)printf("%d
",get_h_del());
else if(op==3)printf("%d
",get_l_del());
}
return 0;
}