Splay真正强大的地方是进行各种神奇的区间操作。
因为splay树是一棵二叉搜索树，所以树的中序遍历一定是有序的，如果我们打破二叉搜索树的性质，把我们需要维护的序列放到树的中序遍历上，就可以区间的各种维护了。
一般来说会有固定的几个步骤：
1、建树。
类似于线段树，二分的不断建就可以了。
int build(int l,int r,int pa) {
if(l>r) return 0;
int mid=(l+r)>>1;
int now=++tot_size;
val[now]=a[mid];
fa[now]=pa;
size[now]=1;
int lson=build(l,mid-1,now);
int rson=build(mid+1,r,now);
ch[now][0]=lson;
ch[now][1]=rson;
update(now);
return now;
}
2、区间操作。
假设我们需要维护的区间为[l,r]，那么我们就把l-1旋转到根，把r+1旋转到根的右儿子，那么区间[l,r]就被我们转移到了r+1的左儿子上了（假设序列有序，手动画一棵树就可以看出），需要手动添加两个端点防止操作[1,n]的时候无法找到l-1和r+1。操作时一般会用lazy标记节省时间。
3、中序遍历的输出序列。
区间翻转
交换左右儿子即可，注意每次查询和输出都要下放标记。
文艺平衡树（Splay）
题目描述
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
输入格式
第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数 接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n
输出格式
输出一行n个数字，表示原始序列经过m次变换后的结果
输入样例
5 3
1 3
1 3
1 4
输出样例
4 3 2 1 5
说明
N,M<=100000
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 100005
#define INF 0x7fffffff
using namespace std;
int read() {
int x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int fa[MAXN],ch[MAXN][2],val[MAXN],size[MAXN],rev[MAXN],root,tot_size;
int n,m,a[MAXN];
int get(int x) {
return x==ch[fa[x]][1];
}
void update(int x) {
size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
void push_rev(int x) {
if(rev[x]) {
swap(ch[x][0],ch[x][1]);
rev[ch[x][0]]^=1;
rev[ch[x][1]]^=1;
rev[x]=0;
}
}
void connect(int x,int pa,int which) {
fa[x]=pa;
ch[pa][which]=x;
}
void rotate(int x) {
int which=get(x),pa=fa[x],papa=fa[pa];
connect(ch[x][!which],pa,which);
connect(pa,x,!which);
connect(x,papa,ch[papa][1]==pa);
update(pa);
update(x);
}
void splay(int x,int rt) {
for(int pa;(pa=fa[x])!=rt;rotate(x)) {
if(fa[pa]!=rt) rotate(get(pa)==get(x)?pa:x);
}
if(rt==0) root=x;
}
int build(int l,int r,int pa) {
if(l>r) return 0;
int mid=(l+r)>>1;
int now=++tot_size;
val[now]=a[mid];
fa[now]=pa;
size[now]=1;
int lson=build(l,mid-1,now);
int rson=build(mid+1,r,now);
ch[now][0]=lson;
ch[now][1]=rson;
update(now);
return now;
}
int find(int x) {
int now=root;
while(true) {
push_rev(now);
if(x<=size[ch[now][0]]) {
now=ch[now][0];
}
else {
x-=size[ch[now][0]]+1;
if(!x) return now;
now=ch[now][1];
}
}
}
void flip(int l,int r) {
int L=find(l),R=find(r+2);
splay(L,0);
splay(R,L);
rev[ch[ch[root][1]][0]]^=1;
}
void output(int x) {
push_rev(x);
if(ch[x][0]) output(ch[x][0]);
if(val[x]!=-INF && val[x]!=INF) printf("%d ",val[x]);
if(ch[x][1]) output(ch[x][1]);
}
int main() {
n=read(),m=read();
a[1]=-INF;
a[n+2]=INF;
for(int i=1;i<=n;i++) a[i+1]=i;
root=build(1,n+2,root);
while(m--) {
int l=read(),r=read();
flip(l,r);
}
output(root);
return 0;
}
区间修改&区间求和
新建sum[]记录区间和，然后类似于线段树的操作。
题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上x
2.求出某区间每一个数的和
输入格式：
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
输出格式：
输出包含若干行整数，即为所有操作2的结果。
输入样例：
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
输出样例#1：
11
8
20
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强，保证在int64/long long数据范围内）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100005
#define ll long long
#define INF 9223372036854775807LL
using namespace std;
ll read() {
ll x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll fa[MAXN],ch[MAXN][2],size[MAXN],val[MAXN],sum[MAXN],col[MAXN],tot_size,root;
ll n,m,a[MAXN];
void update(ll x) {
size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];
}
int get(ll x) {
return ch[fa[x]][1]==x;
}
void color(int rt,int x) {
col[rt]+=x;
val[rt]+=x;
sum[rt]+=x*size[rt];
}
void push_col(ll x) {
if(col[x]) {
if(ch[x][0]) color(ch[x][0],col[x]);
if(ch[x][1]) color(ch[x][1],col[x]);
col[x]=0;
}
}
void connect(ll x,ll pa,int which) {
fa[x]=pa;
ch[pa][which]=x;
}
void rotate(ll x) {
ll pa=fa[x],papa=fa[pa];
int which=get(x);
connect(ch[x][!which],pa,which);
connect(pa,x,!which);
connect(x,papa,ch[papa][1]==pa);
update(pa);
update(x);
return;
}
void splay(ll x,ll rt) {
for(int pa;(pa=fa[x])!=rt;rotate(x)) {
if(fa[pa]!=rt) rotate(get(x)==get(pa)?pa:x);
}
if(rt==0) root=x;
}
ll build(ll l,ll r,ll pa) {
if(l>r) return 0;
int mid=(l+r)>>1;
int now=++tot_size;
val[now]=a[mid];
fa[now]=pa;
size[now]=1;
int lson=build(l,mid-1,now);
int rson=build(mid+1,r,now);
ch[now][0]=lson;
ch[now][1]=rson;
update(now);
return now;
}
ll find(ll x) {
ll now=root;
while(true) {
push_col(now);
if(x<=size[ch[now][0]]) {
now=ch[now][0];
}
else {
x-=size[ch[now][0]]+1;
if(!x) return now;
now=ch[now][1];
}
}
}
ll split(ll l,ll r) {
ll L=find(l),R=find(r+2);
splay(L,0);
splay(R,root);
return ch[ch[root][1]][0];
}
void make_same(ll l,ll r,ll x) {
color(split(l,r),x);
}
ll get_sum(ll l,ll r) {
return sum[split(l,r)];
}
int main() {
n=read(),m=read();
a[1]=-INF;
a[n+2]=INF;
for(int i=1;i<=n;i++) a[i+1]=read();
root=build(1,n+2,root);
while(m--) {
int opt=read();
if(opt==1) {
ll l=read(),r=read(),x=read();
make_same(l,r,x);
}
else {
ll l=read(),r=read();
printf("%lld\n",get_sum(l,r));
}
}
return 0;
}
一切有关线段树的题目都可以用这种方法同理操作。
区间截取（区间删除&区间插入）
题目大意
[1,n]的数列，m次操作，需要维护两种操作。
1、CUT（l,r,c）区间截取：
把[l,r]截下来然后放到剩余数的第c个数的后面。
2、FLIP（l,r）区间翻转。
截取区间就直接截就好了，再插入进去的时候是把c转到根，c+1转到根的右儿子，然后在c+1的左儿子上直接插入。
这里因为加了一个虚拟节点，就找c+1和c+2。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 300005
#define INF 0x7fffffff
#define rlson ch[ch[root][1]][0]
using namespace std;
int read() {
int x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int fa[MAXN],ch[MAXN][2],val[MAXN],size[MAXN],rev[MAXN],a[MAXN],tot_size,root;
int n,m;
void clear(int x) {
fa[x]=ch[x][0]=ch[x][1]=val[x]=size[x]=rev[x]=0;
}
void update(int x) {
size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
int get(int x) {
return ch[fa[x]][1]==x;
}
void push_rev(int x) {
if(rev[x]) {
swap(ch[x][0],ch[x][1]);
rev[ch[x][0]]^=1;
rev[ch[x][1]]^=1;
rev[x]=0;
}
}
void connect(int x,int f,int which) {
fa[x]=f;
ch[f][which]=x;
}
void rotate(int x) {
int f=fa[x],ff=fa[f],which=get(x);
connect(ch[x][!which],f,which);
connect(f,x,!which);
connect(x,ff,ch[ff][1]==f);
update(f);
update(x);
}
void splay(int x,int rt) {
for(int f;(f=fa[x])!=rt;rotate(x)) {
if(fa[f]!=rt) rotate(get(x)==get(f)?f:x);
}
if(!rt) root=x;
}
int build(int l,int r,int f) {
if(l>r) return 0;
int mid=(l+r)>>1;
int now=++tot_size;
val[now]=a[mid];
fa[now]=f;
size[now]=1;
int lson=build(l,mid-1,now);
int rson=build(mid+1,r,now);
ch[now][0]=lson;
ch[now][1]=rson;
update(now);
return now;
}
int find(int x) {
int now=root;
while(true) {
push_rev(now);
if(x<=size[ch[now][0]]) {
now=ch[now][0];
}
else {
x-=size[ch[now][0]]+1;
if(!x) return now;
now=ch[now][1];
}
}
}
int split(int l,int r) {
int L=find(l),R=find(r+2);
splay(L,0);
splay(R,L);
return rlson;
}
void cut(int l,int r,int c) {
int del=split(l,r);
rlson=0;
int gg=split(c+1,c+2);
rlson=del;
fa[del]=ch[root][1];
}
void flip(int l,int r) {
rev[split(l,r)]^=1;
}
void output(int x) {
push_rev(x);
if(ch[x][0]) output(ch[x][0]);
if(val[x]!=-INF && val[x]!=INF) printf("%d ",val[x]);
if(ch[x][1]) output(ch[x][1]);
}
int main() {
n=read(),m=read();
a[1]=-INF,a[n+2]=INF;
for(int i=1;i<=n;i++) a[i+1]=i;
root=build(1,n+2,root);
while(m--) {
string s;
cin>>s;
if(s[0]=='C') {
int l=read(),r=read(),c=read();
cut(l,r,c);
}
else {
int l=read(),r=read();
flip(l,r);
}
}
output(root);
return 0;
}
如果单独的区间删除和插入的话，和这个方法类似，删除的时候把=0改成直接clear()就好了，插入需要把需要插入的区间建一棵新树再插入。
end.
