http://blog.csdn.net/acm_cxlove/article/details/7815019 附上cxlove大神的博客链接，最近是跟着上面的题目做的。
刚学的时候感觉好难，显示照着大白皮上面敲的模板，然后网上各种看论文，感觉指针写还是太繁琐，还是直接数组写的精炼。感觉Splay树确实强大，可以解决好多序列问题。感觉Splay树的核心是Key_Tree = ch[ch[root][1]][0]这个东西的使用，因为这棵子树就代表了你当前要修改，或者查询的区间，当然单点修改也可以这样做。
Splay树的核心操作有两个：一个是Splay操作（把当前点转到根节点的操作），一个是把第k个点转到根（其实不一定是根）。
下面附上这两种操作的模板：
kind == 0 表示左旋，kind == 1表示右旋
void Rotate(int x,int kind){
int y = pre[x];
Push_Down(y);
Push_Down(x);
ch[y][!kind] = ch[x][kind];
pre[ch[x][kind]] = y;
if(pre[y]){
ch[pre[y]][ch[pre[y]][1] == y] = x;
}
pre[x] = pre[y];
ch[x][kind] = y;
pre[y] = x;
Push_Up(y);
} //把x节点旋转到goal下面
void Splay(int x,int goal){
Push_Down(x);
while(pre[x] != goal){
Push_Down(pre[pre[x]]); Push_Down(pre[x]); Push_Down(x);
if(pre[pre[x]] == goal){
Rotate(x,ch[pre[x]][0] == x);
}
else{
int y = pre[x];
int kind = (ch[pre[y]][0] == y);
if(ch[y][kind] == x){
Rotate(x,!kind);
Rotate(x,kind);
}
else{
Rotate(y,kind);
Rotate(x,kind);
}
}
}
Push_Up(x);
if(!goal) root = x;
} ///把第k个节点转到goal下面
void RotateTo(int k,int goal){
int x = root;
Push_Down(x);
while(sz[ch[x][0]] != k){
if(k < sz[ch[x][0]]){
x = ch[x][0];
}
else{
k -= (sz[ch[x][0]]+1);
x = ch[x][1];
}
Push_Down(x);
}
Splay(x,goal);
}上面的模板入门不能好好理解得话，画几张图就会了。
区间操作的时候，查询或者修改[l,r]这段区间，那么我们把RotateTo(l-1,0),RotateTo(r+1,root)那么，此时Key_Tree的子树就代表这段要查询或者修改的区间。这个是伸展树里面区间操作的核心的核心！！！
然后区间操作还有一个关键的地方就是：Push_Up,Push_Down操作，和线段树很像。还有就是初始化了，一般我都是在序列头，序列尾多加一个节点，这样就能保证不会越界了，还有就是初始化的时候最好把0这种节点的值附为一个不会影响答案的值。
下面附上几道题目（可以跟着练手）：
HYSBZ 1588 营业额统计：
HDU 3436 Queue_jumpers
这题主要要把一个区间缩成一个点。写起来可能稍微麻烦一点
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#define LL long long
#define FOR(i,x,y) for(int i = x;i < y;i ++)
#define IFOR(i,x,y) for(int i = x;i > y;i --)
#define Key_Tree ch[ch[root][1]][0]
#define MAXN 110000
using namespace std;
int n,m;
int TQ[MAXN],cnt_TQ;
int N,ssz[MAXN],l[MAXN];
map <int,int> mat;
struct Commends{
char str[10];
int num;
}cmd[MAXN];
struct SplayTree{
int ch[MAXN][2],sz[MAXN],pre[MAXN],key[MAXN],root,tot,sum[MAXN],val[MAXN],pos[MAXN];
int flip[MAXN];
void Rotate(int x,int kind){
int y = pre[x];
Push_Down(y);
Push_Down(x);
ch[y][!kind] = ch[x][kind];
pre[ch[x][kind]] = y;
if(pre[y]){
ch[pre[y]][ch[pre[y]][1] == y] = x;
}
pre[x] = pre[y];
ch[x][kind] = y;
pre[y] = x;
Push_Up(y);
}
void Splay(int x,int goal){
Push_Down(x);
while(pre[x] != goal){
Push_Down(pre[pre[x]]); Push_Down(pre[x]); Push_Down(x);
if(pre[pre[x]] == goal){
Rotate(x,ch[pre[x]][0] == x);
}
else{
int y = pre[x];
int kind = (ch[pre[y]][0] == y);
if(ch[y][kind] == x){
Rotate(x,!kind);
Rotate(x,kind);
}
else{
Rotate(y,kind);
Rotate(x,kind);
}
}
}
Push_Up(x);
if(!goal) root = x;
}
void RotateTo(int k,int goal){
int x = root;
Push_Down(x);
while(sz[ch[x][0]] != k){
if(k < sz[ch[x][0]]){
x = ch[x][0];
}
else{
k -= (sz[ch[x][0]]+1);
x = ch[x][1];
}
Push_Down(x);
}
Splay(x,goal);
}
//debug部分copy from hh
void Treaval(int x) {
if(x) {
Treaval(ch[x][0]);
printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,key = %2d,sum = %2d,val = %2d
",x,ch[x][0],ch[x][1],pre[x],sz[x],key[x],sum[x],val[x]);
Treaval(ch[x][1]);
}
}
void debug() {printf("%d
",root);Treaval(root);}
//以上debug
void NewNode(int& x,int father,int k,int v){
x = ++tot;
pre[x] = father;
key[x] = k;
val[x] = v;
ch[x][0] = ch[x][1] = 0;
sz[x] = 1;
flip[x] = 0;
}
void Push_Up(int x){
sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
sum[x] = sum[ch[x][0]]+ sum[ch[x][1]] + val[x];
}
void Push_Down(int x){
if(flip[x]){
flip[ch[x][0]] ^= 1;
flip[ch[x][1]] ^= 1;
flip[x] = 0;
swap(ch[x][1],ch[x][0]);
}
}
void Build(int& x,int l,int r,int father){
if(l > r) return;
int mid = (l+r) >> 1;
NewNode(x,father,mid,ssz[mid]);
pos[mid] = x;
Build(ch[x][0],l,mid-1,x);
Build(ch[x][1],mid+1,r,x);
Push_Up(x);
}
void Init(){
root = tot = 0;
ch[0][1] = ch[0][0] = pre[0] = sz[0] = 0;
NewNode(root,0,0,1);
NewNode(ch[root][1],root,0,1);
sz[root] = 2;
Build(Key_Tree,1,N,ch[root][1]);
Push_Up(ch[root][1]);
Push_Up(root);
}
void UpDate(int x){
ch[x][1] = ch[x][0] = 0;
sz[x] = 1;
sum[x] = val[x];
}
void Top(int x){
RotateTo(0,0);
Splay(x,root);
int a = Get_Pre(x);
if(a == -1) return;
Splay(a,x);
pre[Key_Tree] = root;
pre[ch[ch[root][1]][1]] = Key_Tree;
ch[Key_Tree][1] = ch[ch[root][1]][1];
ch[root][1] = Key_Tree;
Push_Up(ch[root][1]);
Push_Up(root);
UpDate(x);
RotateTo(1,root);
pre[x] = ch[root][1];
Key_Tree = x;
Push_Up(ch[root][1]);
Push_Up(root);
}
int Query(int x){
//debug();
Splay(x,root);
return sum[Key_Tree]+1;
}
int Rank(int x,int k){
if(k >= sum[ch[x][0]] && k < sum[ch[x][0]] + val[x])
return (l[key[x]] + k - (sum[ch[x][0]]));
if(k < sum[ch[x][0]])
return Rank(ch[x][0],k);
return Rank(ch[x][1],k - (sum[ch[x][0]] + val[x]));
}
void solve(){
//debug();
FOR(i,0,m){
if(cmd[i].str[0] == 'T') {Top(pos[mat[cmd[i].num]]);}
else if(cmd[i].str[0] == 'Q') {printf("%d
",Query(pos[mat[cmd[i].num]]));}
else {printf("%d
",Rank(root,cmd[i].num));}
}
}
int Get_Pre(int x){
Push_Down(x);
x = ch[x][0];
while(x){
Push_Down(x);
while(ch[x][1]){
x = ch[x][1];
Push_Down(x);
}
return x;
}
return -1;
}
int Get_Next(int x){
Push_Down(x);
x = ch[x][1];
while(x){
Push_Down(x);
while(ch[x][0]){
x = ch[x][0];
Push_Down(x);
}
return x;
}
return -1;
}
}spt;
void Read(){
cnt_TQ = 0;
FOR(i,0,m){
scanf("%s%d",cmd[i].str,&cmd[i].num);
if(cmd[i].str[0] != 'R'){
TQ[cnt_TQ ++] = cmd[i].num;
}
}
sort(TQ,TQ+cnt_TQ);
N = 0;
if(TQ[0] == 1){
mat[1] = 1;
ssz[++N] = 1;
l[N] = 1;
}
else{
ssz[++N] = TQ[0]-1;
l[N] = 1;
mat[TQ[0]] = ++N;
ssz[N] = 1;
l[N] = TQ[0];
}
FOR(i,1,cnt_TQ){
if(TQ[i] == TQ[i-1]) continue;
if(TQ[i] == TQ[i-1] + 1){
mat[TQ[i]] = ++N;
ssz[N] = 1;
l[N] = TQ[i];
}
else{
ssz[++N] = TQ[i] - TQ[i-1]-1;
l[N] = TQ[i-1] + 1;
mat[TQ[i]] = ++N;
ssz[N] = 1;
l[N] = TQ[i];
}
}
if(TQ[cnt_TQ-1] != n){
ssz[++N] = n - TQ[cnt_TQ-1];
l[N] = TQ[cnt_TQ-1] + 1;
}
}
int main()
{
//freopen("test.in","r",stdin);
int T,tCase = 0;
scanf("%d",&T);
while(T--){
printf("Case %d:
",++tCase);
scanf("%d%d",&n,&m);
Read();
spt.Init();
spt.solve();
}
return 0;
}HDU 1890 Robotic Sort
HDU 3487 Play With Chain
没什么难的地方：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define LL long long
#define FOR(i,x,y) for(int i = x;i < y;i ++)
#define IFOR(i,x,y) for(int i = x;i > y;i --)
#define Key_Tree ch[ch[root][1]][0]
#define MAXN 330000
using namespace std;
int n,m,num[MAXN],cnt;
char cmd[10];
struct SplayTree{
int ans[MAXN];
int ch[MAXN][2],sz[MAXN],pre[MAXN],key[MAXN],root,tot;
int flip[MAXN];
void Rotate(int x,int kind){
int y = pre[x];
Push_Down(y);
Push_Down(x);
ch[y][!kind] = ch[x][kind];
pre[ch[x][kind]] = y;
if(pre[y]){
ch[pre[y]][ch[pre[y]][1] == y] = x;
}
pre[x] = pre[y];
ch[x][kind] = y;
pre[y] = x;
Push_Up(y);
}
void Splay(int x,int goal){
Push_Down(x);
while(pre[x] != goal){
Push_Down(pre[pre[x]]); Push_Down(pre[x]); Push_Down(x);
if(pre[pre[x]] == goal){
Rotate(x,ch[pre[x]][0] == x);
}
else{
int y = pre[x];
int kind = (ch[pre[y]][0] == y);
if(ch[y][kind] == x){
Rotate(x,!kind);
Rotate(x,kind);
}
else{
Rotate(y,kind);
Rotate(x,kind);
}
}
}
Push_Up(x);
if(!goal) root = x;
}
void RotateTo(int k,int goal){
int x = root;
Push_Down(x);
while(sz[ch[x][0]] != k){
if(k < sz[ch[x][0]]){
x = ch[x][0];
}
else{
k -= (sz[ch[x][0]]+1);
x = ch[x][1];
}
Push_Down(x);
}
Splay(x,goal);
}
//debug部分copy from hh
void Treaval(int x) {
if(x) {
Treaval(ch[x][0]);
printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,val = %2d
",x,ch[x][0],ch[x][1],pre[x],sz[x],key[x]);
Treaval(ch[x][1]);
}
}
void Debug() {printf("%d
",root);Treaval(root);}
//以上debug
void Build(int& x,int l,int r,int father){
if(l > r) return;
int mid = (l+r) >> 1;
NewNode(x,father,num[mid]);
Build(ch[x][0],l,mid-1,x);
Build(ch[x][1],mid+1,r,x);
Push_Up(x);
}
void Init(){
root = tot = 0;
ch[0][1] = ch[0][0] = pre[0] = sz[0] = 0;
NewNode(root,0,0);
NewNode(ch[root][1],root,0);
sz[root] = 2;
Build(Key_Tree,0,n-1,ch[root][1]);
Push_Up(ch[root][1]);
Push_Up(root);
}
int Get_Pre(int x){
Push_Down(x);
x = ch[x][0];
while(x){
Push_Down(x);
while(ch[x][1]){
x = ch[x][1];
Push_Down(x);
}
return x;
}
return -1;
}
int Get_Next(int x){
Push_Down(x);
x = ch[x][1];
while(x){
Push_Down(x);
while(ch[x][0]){
x = ch[x][0];
Push_Down(x);
}
return x;
}
return -1;
}
void NewNode(int& x,int father,int k){
x = ++tot;
pre[x] = father;
key[x] = k;
ch[x][0] = ch[x][1] = 0;
sz[x] = 1;
flip[x] = 0;
}
void Push_Up(int x){
sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
}
void Push_Down(int x){
if(flip[x]){
flip[ch[x][0]] ^= 1;
flip[ch[x][1]] ^= 1;
flip[x] = 0;
swap(ch[x][1],ch[x][0]);
}
}
void Flip(int l,int r){
RotateTo(l-1,0);
RotateTo(r+1,root);
flip[Key_Tree] ^= 1;
}
void Cut(int l,int r,int k){
RotateTo(l-1,0);
RotateTo(r+1,root);
int p = Key_Tree;
ch[ch[root][1]][0] = 0;
sz[ch[root][1]] = sz[ch[ch[root][1]][1]] + 1;
Push_Up(root);
//Debug();
RotateTo(k,0);
RotateTo(k+1,root);
pre[p] = ch[root][1];
ch[ch[root][1]][0] = p;
Push_Up(ch[root][1]);
Push_Up(root);
}
void Print(int x){
Push_Down(x);
if(ch[x][0]) {Print(ch[x][0]);}
if(cnt == 0 && key[x] != 0) {printf("%d",key[x]);cnt++;}
else if(key[x] != 0)
{printf(" %d",key[x]);cnt++;}
if(ch[x][1]) {Print(ch[x][1]);}
}
}spt;
int main()
{
//freopen("test.in","r",stdin);
while(~scanf("%d%d",&n,&m) && (n >= 0 || m >= 0)){
FOR(i,0,n) num[i] = i+1;
spt.Init();
//spt.Debug();
FOR(i,0,m){
scanf("%s",cmd);
int l,r,k;
if(cmd[0] == 'C'){
scanf("%d%d%d",&l,&r,&k);
spt.Cut(l,r,k);
//spt.Debug();
}
else{
scanf("%d%d",&l,&r);
spt.Flip(l,r);
}
}
cnt = 0;
spt.Print(spt.root);
printf("
");
}
return 0;
}POJ 3580 SuperMemo
NOI 2005 维修数列
非常BT的一题
版权声明：本文为博主原创文章，未经博主允许不得转载。