2019/7/16更新：封装SplayTree进入class：例题：http://poj.org/problem?id=3622
一个伸展树的板子：
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
// srand(unsigned)time(NULL));rand();
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
#define ll long long
#define Pair pair<int,int>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXN=1e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)
class SplayTree{
struct Node{
ll A,B;
int l,r,f,siz;
Node(ll _A=0,ll _B=0,int _l=0,int _r=0,int _f=0,int _siz=0){
A=_A;B=_B;l=_l;r=_r;f=_f;siz=_siz;
}
friend int operator < (Node a,Node b){
if(a.A==b.A) return a.B<b.B;
return a.A<b.A;
}
};
Node Tree[MAXN];
int Lazy[MAXN];
int Rt,Ecnt;//Rt的父节点是0,第一个节点从1开始。
void PushUp(int x){//次序
Tree[x].siz=Tree[Tree[x].l].siz+Tree[Tree[x].r].siz+1;
}
void PushDown(int x){//反转
if(Lazy[x]){
int temp=Tree[x].l;Tree[x].l=Tree[x].r;Tree[x].r=temp;
Lazy[Tree[x].l]^=1;Lazy[Tree[x].r]^=1;
Lazy[x]=0;
}
}
void Rotate(int x,int oper){
int y=Tree[x].f;
PushDown(y);PushDown(x);
if(oper){
Tree[y].r=Tree[x].l;
if(Tree[x].l!=0) Tree[Tree[x].l].f=y;
Tree[x].l=y;
}
else{
Tree[y].l=Tree[x].r;
if(Tree[x].r!=0) Tree[Tree[x].r].f=y;
Tree[x].r=y;
}Tree[x].f=Tree[y].f;
if(Tree[y].f){
if(y==Tree[Tree[y].f].l) Tree[Tree[y].f].l=x;
else Tree[Tree[y].f].r=x;
}Tree[y].f=x;PushUp(y);
}
void Splay(int x,int f){
PushDown(x);
int y=Tree[x].f,z=0;
while(y!=f){
z=Tree[y].f;
PushDown(z);PushDown(y);PushDown(x);
if(z==f) Rotate(x,x==Tree[y].r);
else{
if((x==Tree[y].l^y==Tree[z].l)==0){
Rotate(y,y==Tree[z].r);Rotate(x,x==Tree[y].r);
}
else{
Rotate(x,x==Tree[y].r);Rotate(x,x==Tree[z].r);
}
}PushUp(x);y=Tree[x].f;
}PushUp(x);
if(f==0) Rt=x;
}
int MinNode(ll Key){
int x=Rt,ans=-1;
PushDown(x);
while(1){
if(Tree[x].A>=Key){//该节点可以取得
ans=x;
if(Tree[x].l) x=Tree[x].l;//向左子节点
else return ans;
}
else{//不可以取得
if(Tree[x].r) x=Tree[x].r;//可以的话直接向右走了
else return ans;//没有符合要求的
}
}
}
int GetPre(){
int x=Rt;
if(Tree[x].l) x=Tree[x].l;
else return x;
while(1){
if(Tree[x].r) x=Tree[x].r;
else return x;
}
}
public:
void Intt(){
clean(Lazy,0);
Rt=0;Ecnt=0;
}
void Insert(ll A,ll B){
Tree[++Ecnt]=Node(A,B,0,0,0,1);
int y=0,x=Rt;
while(x){
y=x;
if(Tree[Ecnt]<Tree[x]) x=Tree[x].l;
else if(Tree[x]<Tree[Ecnt]) x=Tree[x].r;
else return ;
}
if(y==0) Rt=Ecnt;
else if(Tree[Ecnt]<Tree[y]){
Tree[y].l=Ecnt;Tree[Ecnt].f=y;
}
else{
Tree[y].r=Ecnt;Tree[Ecnt].f=y;
}Splay(Ecnt,0);
}
ll DeleteMin(ll Key){//所有的B都符合要求，找到最小的A>=P
int Pos=MinNode(Key);
if(Pos==-1) return -1;
ll Ans=Tree[Pos].A;
Splay(Pos,0);
//cout<<"Pos,Pre:"<<Pos<<" "<<GetPre()<<endl;
Splay(GetPre(),0);//cout<<"Debug:\n";Show(Rt);cout<<"End\n";
if(Pos==GetPre()){
Rt=Tree[Rt].r;Tree[Rt].f=0;
}
else{
Splay(Pos,Rt);
Tree[Rt].r=Tree[Pos].r;Tree[Tree[Rt].r].f=Rt;
}
return Ans;
}
//-------
int GetRt(){
return Rt;
}
void Show(int x){
if(x==0) return ;
PushDown(x);
printf("x:%d xf:%d xl:%d xr:%d (A,B)(%lld,%lld)\n",x,Tree[x].f,Tree[x].l,Tree[x].r,Tree[x].A,Tree[x].B);
Show(Tree[x].l);
// printf("A:%lld B:%lld\n",Tree[x].A,Tree[x].B);
Show(Tree[x].r);
}
};
struct Node{
ll P,G;
Node(ll _P=0,ll _G=0){
P=_P;G=_G;
}
friend int operator < (Node a,Node b){
if(a.G==b.G) return a.P<b.P;
return a.G<b.G;
}
};
SplayTree Spl;
Node Cows[MAXN],Goods[MAXN];
int n,m;
int PosX(ll Key,int l,int r){
while(l<=r){
int mid=(l+r)>>1;
if(Goods[mid].G<Key) l=mid+1;
else r=mid-1;
}return l;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%lld%lld",&Cows[i].P,&Cows[i].G);
for(int i=1;i<=m;++i) scanf("%lld%lld",&Goods[i].P,&Goods[i].G);
sort(Cows+1,Cows+1+n);sort(Goods+1,Goods+1+m);
ll ans=0;int flag=1,tmp=m;
Spl.Intt();
for(int i=n;i>=1;--i){
int Pos=PosX(Cows[i].G,1,tmp);
for(int j=Pos;j<=tmp;++j) Spl.Insert(Goods[j].P,Goods[j].G);
ll temp=Spl.DeleteMin(Cows[i].P);
if(temp==-1){//找最小的花费
flag=0;break;
}ans+=temp;tmp=Pos-1;
}
if(flag==0) printf("-1\n");
else printf("%lld\n",ans);
}
在开头写下伸展树的应用情况，以及使用方法，由于本人是个蒟蒻，因此总结不为全面，有更多的方法希望指出和提醒：
对于伸展树的一些应用：
因为伸展树和核心是 旋转节点 ，所以我们就从旋转节点处开始入手，进行一些 骚操作。
1.裸的伸展树，实现增删改查，对节点的直接操作，比较简单，会板子就行
2.对区间的修改，例：对区间[a,b]修改，
可以将节点a-1旋转到根节点的位置，将b+1旋转到根节点的右子节点，
这样的话，根节点的右子节点的左子树就是区间[a,b];
我们可以直接对于每个节点里面储存的信息进行修改
(节点中可以储存以该节点为根节点的一些信息，修改也好修改，旋转向下传递)
3.在a后面插入一些数，那么我们先把插入的这些数建成一颗伸展树，
用分治法建立一颗完全平衡的二叉树，
就是说每次把最中间的节点转到根节点的右边，
最后将这颗新的子树挂到 根右子节点的左子节点上
4.删除一个区间[a,b]内的数 ，可以参考第二种情况，
旋转，然后直接删除一个一颗子树，继续维护伸展树
5.区间的翻转，对区间[a,b]的翻转，可以引用一个lazy数组进行标记，每次旋转的时候判断一下，翻转则翻转左右子节点，然后向下推一个节点，然后刷新本节点lazy数组。
/*-----------------------伸展树----------------------------*/
伸展数(Splay Tree)，又叫分裂树，是一种二叉排序树，能在O(log n)内完成插入，查找，删除操作；
伸展树上的一般操作都基于伸展操作：
假设要对一个二叉查找树执行一系列查找操作，为使整个查找时间更小，被查效率高的那些条目应当经常处于靠近树根的位置；
于是想设计一个简单方法，在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。
伸展树是一种自调形式的二叉查找树，他会沿着从某个节点到树根之间的路径，通过一系列旋转的把这个节点搬移到树根去。
它的优势在于不需要记录用于平衡树的冗余信息。
关键词：
二叉排序树 平衡树
因此我决定先学这两个数据结构：
//--------------------二叉排序树：
又称 二叉查找树||二叉搜索树
定义：
二叉排序树或者一颗空树，或者具有下列性质的二叉树：
1.若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2.若右子树不空则右子树上所有节点的值均大于它的根节点的值；
3.左右子树分别为二叉排序树；
4.没有 键值 相等的节点
//键值(key)：
//键值是 window 中注册表中的概念。键值位于注册表结构链末端，和文件系统的文件类似；
//键值包含集中数据类型，以适应不同环境的使用需求。
// 注册表中，是通过键和子键来管理各种信息；
简单的说 二叉排序树就是一棵从左往右越来越大的树。
//---查找：
若根节点的关键字等于查找的关键字，成功
否则，判断查找关键字值，递归进入左子树或右子树
子树为空，查找不成功
//---插入删除：
二叉排序树是一种动态树表，其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值时在进行插入。
新插入的节点一定是一个新添加的叶子节点而且查找不成功时查找路径上访问的最后一个节点的左||右子节点
插入算法：
首先执行查找算法，找出被插节点的父节点；
判断被插节点是其父节点的左||右子节点，被插节点作为子节点插入。
若二叉树为空，则首先单独生成根节点。
新插入的节点总是叶子节点。
struct bitree{
int data;
bitree *lchild,*rchild;
};
//在二叉排序树中插入查找关键字key
bitree* insertbst(bitree *t,int key)
{
if(t==NULL)
{
t=new bitree();
t->lchild=t->rchild=NULL;
t->data=key;
return t;
}
if(key<t->data)
t->lchild=insertbst(t->lchild,key);
else
t->rchild=insertbst(t->rchild,key);
return t;
}
//n个数据在数组d中，tree为二叉排序树 树根
bitree* create_bitree(bitree *tree,int d[],int n)
{
for(int i=0;i<n;++i)
tree=insertbst(tree,d[i]);
}
//---删除节点
在二叉排序树中删除一个节点，分成三种情况：
1.若*p节点为叶子节点，即PL(左子树)和PR(右子树)均为空树，由于删去叶子节点不破坏整棵树的结构，则可以直接删除此子节点。
2.若*p节点只有左子树PL或右子树PR，此时只要令PL||PR直接成为其双亲节点*f的左子树(当*p是左子树)或右子树(当*p是右子树) ，此时也不破坏二叉排序树的特性
3. 若*p节点的左子树和右子树均不为空 。在删去*p后，为保持其他元素的相对位置不变，课按中序遍历保持有序进行调整。
有两种做法：
一：令*p左子树为*f的左||右子树(依照*p是*f左子树还是右子树而定)，*s为*p左子树的最右下的节点，而*p的右子树为*s的右子树；
二：令*p的直接前驱(或直接后继)替代*p，然后再从二叉排序树中删去他的直接前驱(直接后继)
--即让*f的左子树(如果有的话)成为*p左子树的最坐下节点(如果有的话)，再让*f成为*p的左右节点的父节点。
直白的说就是：因为二叉查找树的原因，被删节点*p左子树的最右边的节点的值必定小于*p右子树根节点的值 ，
因此可以直接把*p的右子树拼接到*p左子树的最右边的子节点上
算法如下：
bool Delete(bitree*);
bool Deletebst(bitree &tparent,bitree &T,keytype key)
{//若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素，并返回true否则返回false
if(!T)
return false;
else
{
if(key==T->data.key)//找到关键字等于key的数据元素
return Delete(parent_t,t);
else if(key<T->lchild.key)
return Deletebst(T,T->lchild,key);
else
return Deletebst(T,T->rchild,key);
}
return true;
}
bool Delete(bitree &fp,bitree &p)
{//从二叉排序树中删除节点p，并重接它的左||右子树
if(!p->rchild)//只需要连接一棵树即可
{
fp->lchild=p->lchild;
delete(p);
}
else if(!p->lchild)
{
fp->rchild=p->rchild;
delete(p);
}
else//连接两棵树
{
q=p;
fp->lchild=p->lchild;
s=p->lchild;//转左
while(s->rchild)//向右到尽头
{
q=s;
s=s->rchild;
}//此时q是s的父节点
s->rchild=p->rchild;//将s的左子树作为q的右子树
delete(p);
}
return true;
}
//----------------平衡树
平衡二叉树(Balanced Binary Tree)具有以下性质:
它是一颗空树||它的左右两个子树高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。
平衡树的实现方法有：
红黑树，AVL，替罪羊树，Treap，伸展树等
最小平衡二叉树节点的公式：F(n)=F(n-1)/*左子树树节点数量*/+F(n-2)/*右子树节点数量*/+1;
平衡树的维持方法：
二叉左旋：
//待学习。。。
二叉右旋：
//待学习。。。
//---------------------------了解完基础知识，开始学习伸展树--------
如何构造一个伸展树：
//---方法一：
访问到X节点时，从X处单旋转将X移动到根节点处，
也就是将访问路径上的每个节点和他们的父节点都实施旋转 。
这种旋转的效果是将访问节点X一直推向树根，
但是不好的地方是可能将其他节点推向更深的位置，
这种效果并不好，因为它没有改变访问路径上其他节点的后序访问状况。
//---方法二：
和方法一类似，
在访问到节点X时，根据X节点和其父节点(P)以及祖父节点(G)之间的形状做相应的单选转或双旋转。
如果三个节点构成LR或RL时(即之字型)，则进行相应的双旋转；
如果构成LL或者RR时进行对应的单选转(一字型)。
这样展开的效果是将X推向根节点的同时，
访问路径上其他节点的深度大致都减少了一半
(某些浅的节点最多向后退后了两层)。
这样做对绝大多数访问路径上的节点的后续访问都是有益的。
//-----伸展树的基本特性：
当访问路径太长而导致超出正常查找时间的时候，这些旋转将对未来的操作(下一次访问)有益；
当访问耗时很少的时候，这些旋转则不那么有益甚至有害。
/*--一个（舍弃）的 解释
//------伸展树的基本操作
伸展树的伸展方式有两种，一种是自下向上的伸展；另一种是自上向下的伸展。
比较容易理解的是自下向上的伸展，我们会重点解释自顶向下的实现方式。
//---自下向上
先自上向下搜寻X节点，
当搜索到X节点时，从X节点开始到根节点的路径上所有的节点进行旋转 ，
最终将X节点推向根节点，将访问路径上的大部分节点的深度都降低。
具体旋转需根据不同的情形进行，在X节点处有三种情形需要考虑
（假设X的父节点是P，X的祖父节点为G）：
1.X的父节点P就是树根的情形，这种情形比较简单，只需要将X和P进行旋转即可，
X和P构成LL就是左单选转，构成RR就右单旋转
2.X和P和G之间构成"之"字型的情形，即LR||RL类型。
如果是LR则进行左双旋转，如果是RL进行右双旋转 。
3.X和P和G之间构成"一"字形的情形，即RR||LL类型；
如果LL则执行两次单左旋转，如果是RR则执行两次单右旋转；
代码先不写了：效率据说不高
//--自顶向下的伸展
*/ 自顶向下的伸展：
换成图片就是这样：
然后是运行的代码：
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
struct splaytree_node{
int key;
splaytree_node *left,*right;
};
splaytree_node *splaytree_search(splaytree_node *x,int key)//递归查找
{
if(x==NULL||x->key==key)
return x;
if(key<x->key)
return splaytree_search(x->left,key);
else
return splaytree_search(x->right,key);
}
splaytree_node *splaytree_splay(splaytree_node *tree,int key)//旋转
{
splaytree_node N,*l,*r,*c;
if(tree==NULL)
return tree;
N.left=N.right=NULL;
l=r=&N;
while(1)//开始旋转调整
{
//cout<<tree->key<<endl;
if(key<tree->key)//向l方向调整
{
if(tree->left==NULL)//左边没东西了
break;
if(key<tree->left->key)//左边仍有值 && key仍小于
{
c=tree->left;
tree->left=c->right;
c->right=tree;
tree=c;
//现在已经调整过节点 向左旋转一个节点
if(tree->left==NULL)
break;//如果左边没有值了，就结束循环
}
r->left=tree;
r=tree;
tree=tree->left;
}
else if(key>tree->key)//向r方向调整
{
if(tree->right==NULL)
break;
if(key>tree->right->key)
{
c=tree->right;
tree->right=c->left;
c->left=tree;
tree=c;
if(tree->right=NULL)
break;
}
l->right=tree;
l=tree;
tree=tree->right;
}
else// 已经是该节点了
{
break;
}
}
//当亲位置 tree为目标点||最接近目标点
// cout<<tree<<" "<<tree->key<<" "<<tree->left<<" "<<tree->right<<endl;
l->right=tree->left;
r->left=tree->right;
tree->left=N.right;
tree->right=N.left;
// cout<<tree<<" "<<tree->key<<" "<<tree->left<<" "<<tree->right<<endl;
//翻上去
return tree;
}
splaytree_node *creat_splaytree_node(int key,splaytree_node *left,splaytree_node*right)
{
splaytree_node *p;
if((p=(splaytree_node*)malloc(sizeof(splaytree_node)))==NULL)
return NULL;
p->key=key;
p->left=left;
p->right=right;
return p;
}
splaytree_node *insert_node(splaytree_node* tree,splaytree_node *z)
{
splaytree_node *y=NULL;//要插入的目标位置的上一个位置
splaytree_node *x=tree;//要插入的目标位置
while(x!=NULL)
{
y=x;
if(z->key<x->key)
x=x->left;
else if(z->key>x->key)
x=x->right;
else
{
cout<<"Error：此节点已存在！"<<endl;
free(z);
return tree;
}
}
if(y==NULL)//此时是一颗空树，直接返回z即可
tree=z;
else if(z->key<y->key)//y的左节点
y->left=z;
else
y->right=z;//y的右节点
return tree;
}
splaytree_node *splaytree_insert(splaytree_node *tree,int key)//插入
{
//cout<<tree<<" "<<key<<endl;
splaytree_node *z;
z=creat_splaytree_node(key,NULL,NULL);
//cout<<z<<" "<<z->key<<" "<<key<<endl;
if(z==NULL)//创建失败
return tree;
tree=insert_node(tree,z);//插入节点
//cout<<tree->key<<" "<<tree<<endl;
tree=splaytree_splay(tree,key);//旋转节点(维护该树)
return tree;
}
splaytree_node *splaytree_delete(splaytree_node *tree,int key)//删除
{
splaytree_node *x;
if(tree==NULL)
return NULL;
if(splaytree_search(tree,key)==NULL)
return tree;//没有找到
tree=splaytree_splay(tree,key);//旋转为根节点
if(tree->left!=NULL)
{
x=splaytree_splay(tree->left,key);
//将根节点左子树最大的节点旋转为根节点
x->right=tree->right;
}
else
x=tree->right;
free(tree);
return x;
}
void print_splaytree(splaytree_node *tree,int key,int direction)//打印树
{
if(tree!=NULL)
{
if(direction==0)
cout<<tree->key<<" is root"<<endl;
else
cout<<tree->key<<" is "<<key<<" 's "<<direction<<" child"<<endl;
print_splaytree(tree->left,tree->key,-1);
print_splaytree(tree->right,tree->key,1);
}
}
/*
10
1 2 3 4 5 6 7 8 9 10
7
*/
int main()
{
//插入
int n;
cin>>n;
splaytree_node *root=NULL;
int data;
for(int i=1;i<=n;++i)
{
cin>>data;
root=splaytree_insert(root,data);
//cout<<root<<endl;
print_splaytree(root,root->key,0);
}
cout<<"delete a node"<<endl;
cin>>data;
root=splaytree_delete(root,data);
print_splaytree(root,root->key,0);
}
由于自顶向下伸展会导致，节点刷新的时候需要重新刷新，因此，在比较自下至上伸展之后，发现自下向上伸展对节点的维护更加方便，因此，下面学习伸展树的自下向上的伸展：
其实自下而上的伸展和自上而下的类似，直接上板子了：
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<math.h>
//#include<map>
//#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// 水印
//std::ios::sync_with_stdio(false);
const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
struct node{
int id,data,maxval;
node *l,*r,*f;
/*
使用从下到上的伸展方式，多了一个f指针记录父节点的位置
找到要旋转的目标点，
旋转目标点，直到目标点的父节点是目标父节点
*/
};
node *root;
void show(node *x)
{
if(x==NULL)
return;
cout<<x<<" : "<<x->id<<" "<<x->data<<" "<<x->l<<" "<<x->r<<endl;
show(x->l);
show(x->r);
}
void rotate(node *x,bool oper)
{
node *y=x->f;
if(y==NULL)
return ;
if(oper)
{
y->r=x->l;
if(x->l!=NULL)
x->l->f=y;
x->l=y;
}
else
{
y->l=x->r;
if(x->r!=NULL)
x->r->f=y;
x->r=y;
}
x->f=y->f;
if(y->f!=NULL)
{
if(y==y->f->l)
y->f->l=x;
else
y->f->r=x;
}
y->f=x;
if(y==root)
root=x;
updata(y);
updata(x);
}
void splay(node *x,node *f)
{
node *y=x->f,*z=NULL;
while(y!=f)
{
z=y->f;
if(z==f)
{
rotate(x,x==y->r);
}
else
{
if((x==y->l ^ y==z->l)==0)//一字型
{
rotate(y,y==z->r);
rotate(x,x==y->r);
}
else//之字型
{
rotate(x,x==y->r);
rotate(x,x==z->r);
}
}
y=x->f;
}
}
void insert(int id,int data)
{
node *z;
z=(node*)malloc(sizeof(node));
if(z==NULL)
return ;
z->data=data;
z->id=id;
z->maxval=data;
z->l=z->r=z->f=NULL;
node *y=NULL;
node *x=root;
while(x!=NULL)
{
y=x;
if(z->id<x->id)
x=x->l;
else if(z->id>x->id)
x=x->r;
else
return ;
}
if(y==NULL)
root=z;
else if(z->id<y->id)
{
y->l=z;
z->f=y;
}
else
{
z->f=y;
y->r=z;
}
splay(z,NULL);
}
void delete_node(node *x)
{
if(x==NULL)
return ;
delete_node(x->l);
delete_node(x->r);
free(x);
}
int main()
{
std::ios::sync_with_stdio(false);
int n;
while(cin>>n)
{
root=NULL;//每次重置根节点
int data;
insert(0,0);//插入0个
for(int i=1;i<=n;++i)//按照下标建树
{
cin>>data;
insert(i,data);
}
insert(n+1,0);//插入n+1个，防止边界
show(root);
delete_node(root);//注意最后的时候一定要释放空间，否则会MLE
}
} 下面是一个用数组模拟的板子，以后就不用每次都delete了：
就以HDU-3487为例子写的一个板子：
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
//#include<map>
//#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define key_val son[son[root][1]][0]
//根节点 的 右子节点 的 左子节点
typedef long long ll;
const int N = 300010, INF = 0x3f3f3f3f, MOD = 1000000;
//此时记录遍历数据不已固定的id记录数据了，我们用该节点前面有多少节点个个数作为id，时刻刷新id，实现动态可变
int son[N][2], fat[N], siz[N]/*该子树的节点个数包括自身*/;
int key[N]/*节点权值*/, /*val[N],*/ lazy[N];//隋标记
int root, tot, cnt;
int arr[N];
int n, m;
void new_node(int val, int fa, int &x)
{
x = ++tot;
fat[x] = fa, key[x] = val;
siz[x] = 1, lazy[x] = 0;
son[x][0] = son[x][1] = 0;
}
void push_up(int x)//该节点的节点个数等于左右子树的节点个数+1
{// push_up的操作就是刷新 x子树的节点个数
siz[x] = siz[son[x][0]] + siz[son[x][1]] + 1;
}
void push_down(int x)
{// push_down的操作就是刷新该节点是否需要反转
if(lazy[x])//该节点的lazy存在
{
swap(son[x][0], son[x][1]);//交换该节点的左右子树 区间反转
lazy[son[x][0]] ^= 1, lazy[son[x][1]] ^= 1;// 左节点和右节点刷新
lazy[x] = 0;//该节点重置
}
}
void Rotate(int x, int p)
{
int y = fat[x];
push_down(y); push_down(x);
son[y][!p] = son[x][p], fat[son[x][p]] = y;
if(fat[y]) son[fat[y]][son[fat[y]][1]==y] = x;
fat[x] = fat[y];
son[x][p] = y, fat[y] = x;
push_up(y);
}
void splay(int x, int goal)
{
push_down(x);
while(fat[x] != goal)
{
int y = fat[x], z = fat[y];
//在这里下传翻转标记，在rotate里下传标记可能会使树形改变导致旋转出错
push_down(z); push_down(y); push_down(x);
if(fat[y] == goal) Rotate(x, son[y][0] == x);
else
{
int p = son[fat[y]][0] == y;
if(son[y][p] == x) Rotate(x, !p), Rotate(x, p);
else Rotate(y, p), Rotate(x, p);
}
}
push_up(x);
if(goal == 0) root = x;//刷新根节点
}
//int get_prec(int x)
//{
// push_down(x);
// x = son[x][0];
// push_down(x);
// while(son[x][1])
// x = son[x][1], push_down(x);
// return x;
//}
int get_succ(int x)//x传进来，输出x节点的后继
{
push_down(x);
x = son[x][1];//x的右子节点
push_down(x);
while(son[x][0]) //一直向左找
x = son[x][0], push_down(x);
return x;
}
int get_kth(int k)//找到目标元素所在的节点
{
int x = root;//从根节点开始
push_down(x);//刷新该节点
while(true)
{
//这里细数k和siz的作用：
//因为旋转过了，原来的id会混乱，因此此时对节点id的刷新 以该节点为子节点的个数多少为id
//
if(k <= siz[son[x][0]]) //k是该节点的 左子树
x = son[x][0];
else if(k > siz[son[x][0]] + 1) //k不是在该节点的左子树和该节点处
k =k - (siz[son[x][0]] + 1), x = son[x][1];//刷新k，并且x右走
else break;// 找到该节点
push_down(x);
}
return x;
}
//int get_kth(int x, int k)
//{
// push_down(x);
// if(k <= siz[son[x][0]]) return get_kth(son[x][0], k);
// else if(k > siz[son[x][0]] + 1) return get_kth(son[x][1], k - siz[son[x][0]] - 1);
// return x;
//}
void build(int l, int r, int fa, int &x)
{
if(l > r) return;
int mid = (l + r) >> 1;
new_node(mid, fa, x);
build(l, mid-1, x, son[x][0]);
build(mid+1, r, x, son[x][1]);
push_up(x);
}
void cut(int a, int b, int c)//a - b 加到c后面
{
splay(get_kth(a), 0);//把第a位置的节点旋转道根节点
splay(get_kth(b+2), root);//b旋转到根节点的子节点
int tmp = son[son[root][1]][0];//根节点的右子节点的左子节点
son[son[root][1]][0] = 0;//节点变成0 ，此时已经把a~b区间移除
push_up(son[root][1]), push_up(root);
//刷新根节点的右子节点和根节点 ，移除成功
splay(get_kth(c+1), 0);//旋转c+1节点为跟节点
splay(get_succ(root), root);// 旋转根节点的 后继为子节点（清空根节点的右子节点的左子树）
son[son[root][1]][0] = tmp, fat[son[son[root][1]][0]] = son[root][1];//a - b 子树挂上去
push_up(son[root][1]), push_up(root);//刷新节点
}
void rev(int a, int b)//反转a - b区间
{
splay(get_kth(a), 0);//旋转a到根节点
splay(get_kth(b+2), root);//旋转b 到根节点的右子节点
lazy[son[son[root][1]][0]] ^= 1;//根节点的右子节点 的左子树 隋标记
}
void inorder(int x)//输出序列 中序遍历
{
if(! x) return;//x子树为空
push_down(x);//刷新x
inorder(son[x][0]);//递归找左子节点
if(key[x] > 0) //当前节点 存在
printf("%d%c", key[x], ++cnt == n ? '\n' : ' ');//输出该节点，并且判断是否换行
inorder(son[x][1]);// 递归右子节点
}
void init()
{
root = tot = 0;
son[0][0] = son[0][1] = siz[0] = fat[0] = 0;
key[0] = /*val[0] =*/ lazy[0] = 0;
new_node(-INF, 0, root);//插入两个边界值，然后把序列插入两个边界值之间
new_node(-INF, root, son[root][1]);
build(1, n, son[root][1], son[son[root][1]][0]);//1~n
push_up(son[root][1]), push_up(root);
}
int main()
{
char op[10];
int a, b, c;
while(scanf("%d%d", &n, &m), n != -1 || m != -1)
{
init();
for(int i = 1; i <= m; i++)
{
scanf(" %s%d%d", op, &a, &b);
if(op[0] == 'C')
{
scanf("%d", &c);
cut(a, b, c);//a - b 区间加到c后面
}
else rev(a, b);//反转 a - b 区间
}
cnt = 0;
inorder(root);//输出最终序列
}
return 0;
} 然后是我用子节的那个板子修改的结构体版，最后是格式错误，但是答案是对的，而且时间也差不多：
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<math.h>
//#include<map>
//#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// 水印
//std::ios::sync_with_stdio(false);
const int MAXN=3e5+10;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
struct node{
int siz,val;
int l,r,f;
}tree[MAXN];
int root,ecnt;
bool lazy[MAXN];
int n,m;
void intt()
{
clean(tree,0);
clean(lazy,0);
root=0;
ecnt=0;
}
void push_up(int x)
{
tree[x].siz=tree[tree[x].l].siz+tree[tree[x].r].siz+1;
//cout<<tree[x].siz<<endl;
}
void push_down(int x)
{
if(lazy[x])
{
int temp=tree[x].l;
tree[x].l=tree[x].r;
tree[x].r=temp;
lazy[tree[x].l]^=1;
lazy[tree[x].r]^=1;
lazy[x]=0;
}
}
void rotate(int x,bool oper)
{
int y=tree[x].f;
push_down(y);
push_down(x);
if(oper)
{
tree[y].r=tree[x].l;
if(tree[x].l!=0)
tree[tree[x].l].f=y;
tree[x].l=y;
}
else
{
tree[y].l=tree[x].r;
if(tree[x].r!=0)
tree[tree[x].r].f=y;
tree[x].r=y;
}
tree[x].f=tree[y].f;
if(tree[y].f)
{
if(y==tree[tree[y].f].l)
tree[tree[y].f].l=x;
else
tree[tree[y].f].r=x;
}
tree[y].f=x;
// if(y==root)
// root=x;
push_up(y);
}
void splay(int x,int f)
{
push_down(x);
int y=tree[x].f,z=0;
while(y!=f)
{
z=tree[y].f;
push_down(z);
push_down(y);
push_down(x);
if(z==f)
rotate(x,x==tree[y].r);
else
{
if((x==tree[y].l ^ y==tree[z].l)==0)
{
rotate(y,y==tree[z].r);
rotate(x,x==tree[y].r);
}
else
{
rotate(x,x==tree[y].r);
rotate(x,x==tree[z].r);
}
}
push_up(x);
y=tree[x].f;
}
push_up(x);
if(f==0)
root=x;
}
void insert(int val)
{
tree[++ecnt].val=val;
tree[ecnt].siz=1;
tree[ecnt].l=tree[ecnt].r=tree[ecnt].f=0;
int y=0,x=root;
while(x)
{
y=x;
if(tree[x].val>val)
x=tree[x].l;
else if(tree[x].val<val)
x=tree[x].r;
else
return ;
}
if(y==0)
root=ecnt;
else if(val<tree[y].val)
{
tree[y].l=ecnt;
tree[ecnt].f=y;
}
else
{
tree[y].r=ecnt;
tree[ecnt].f=y;
}
splay(ecnt,0);
}
int get_next(int x)
{
push_down(x);
x=tree[x].r;
push_down(x);
while(tree[x].l)
{
x=tree[x].l;
push_down(x);
}
return x;
}
int get_node(int k)
{
int x=root;
push_down(x);
while(1)
{
//cout<<x<<" "<<tree[x].siz<<" "<<tree[x].val<<" "<<k<<endl;
if(k<=tree[tree[x].l].siz)
x=tree[x].l;
else if(k>tree[tree[x].l].siz+1)
{
k=k-(tree[tree[x].l].siz+1);
x=tree[x].r;
}
else
break;
push_down(x);
}
return x;
}
void cut(int a,int b,int c)
{
int str=get_node(a),ed=get_node(b+2);
splay(str,0);
splay(ed,root);
int temp=tree[tree[root].r].l;
tree[tree[root].r].l=0;
push_up(tree[root].r);
push_up(root);
//------------
int key=get_node(c+1);
splay(key,0);
int nex=get_next(root);
splay(nex,root);
tree[tree[root].r].l=temp;
tree[tree[tree[root].r].l].f=tree[root].r;
push_up(tree[root].r);
push_up(root);
}
void show(int x)
{
if(x==0)
return ;
push_down(x);
show(tree[x].l);
if(tree[x].val>0&&tree[x].val<n+1)
printf("%d ",tree[x].val);//cout<<tree[x].val<<" ";
show(tree[x].r);
}
void rev(int a,int b)
{
int str=get_node(a);
//cout<<tree[str].val<<endl;
//cout<<tree[root].val<<endl;show(root);cout<<endl;
splay(str,0);
//cout<<tree[root].val<<endl;show(root);cout<<endl;
//cout<<"get_ed"<<endl;
int ed=get_node(b+2);
//cout<<ed<<" "<<tree[ed].val<<endl;
splay(ed,root);
//cout<<tree[root].val<<endl;(root);cout<<endl;
lazy[tree[tree[root].r].l] ^=1;
}
int main()
{
//std::ios::sync_with_stdio(false);
while(~scanf("%d%d",&n,&m))
{
if(n==-1&&m==-1)
break;
intt();
insert(0);
for(int i=1;i<=n;++i)
insert(i);
insert(n+1);
//show(root);cout<<endl;
char oper[5];
int a,b,c;
while(m--)
{
// for(int i=0;i<=n+1;++i)
// cout<<tree[i].siz<<" ";
// cout<<endl;
scanf("%s%d%d",&oper,&a,&b);
if(oper[0]=='C')
{
scanf("%d",&c);
cut(a,b,c);
}
else
rev(a,b);
//cout<<tree[root].val<<endl;show(root);cout<<endl;
}
show(root);printf("\n");
}
}
/*
8 2
CUT 3 5 4
FLIP 2 6
-1 -1
*/
然后是区间的增加和修改：
以POJ-3468为例（其实这道题用线段树更好，伸展树的话，时间用的会更加长）
ac：4800ms+
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<math.h>
//#include<map>
//#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// 水印
//std::ios::sync_with_stdio(false);
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
struct node{
ll val,id,sumval,size;
int l,r,f;
}tree[MAXN];
int root,ecnt;
ll lazy[MAXN];
int n,m;
void intt()
{
clean(tree,0);
clean(lazy,0);
root=ecnt=0;
}
void push_up(int x)
{
tree[x].sumval=tree[x].val;
tree[x].sumval+=tree[tree[x].r].sumval+tree[tree[x].l].sumval;
tree[x].size=tree[tree[x].l].size+tree[tree[x].r].size+1;
}
void push_down(int x)
{
if(lazy[x])//向下推值
{
tree[x].val+=lazy[x];//刷新该值
tree[tree[x].l].sumval+=lazy[x]*tree[tree[x].l].size;//左子节点刷新
tree[tree[x].r].sumval+=lazy[x]*tree[tree[x].r].size;//右子节点刷新
lazy[tree[x].l]+=lazy[x];
lazy[tree[x].r]+=lazy[x];
lazy[x]=0;
// cout<<"push_down:";
// cout<<tree[x].id<<" "<<tree[x].val<<" "<<tree[x].sumval<<endl;
}
}
void show(int x)
{
if(x==1||x==0)
return ;
push_down(x);
cout<<tree[x].val<<" ";
//cout<<x<<": "<<tree[x].id<<" "<<tree[x].val<<endl;
show(tree[x].l);
show(tree[x].r);
}
void rotate(int x,bool oper)
{
int y=tree[x].f;
push_down(x);
push_down(y);
if(oper)
{
tree[y].r=tree[x].l;
if(tree[x].l!=0)
tree[tree[x].l].f=y;
tree[x].l=y;
}
else
{
tree[y].l=tree[x].r;
if(tree[x].r!=0)
tree[tree[x].r].f=y;
tree[x].r=y;
}
tree[x].f=tree[y].f;
if(tree[y].f)
{
if(y==tree[tree[y].f].l)
tree[tree[y].f].l=x;
else
tree[tree[y].f].r=x;
}
tree[y].f=x;
push_up(y);
}
void splay(int x,int f)
{
push_down(x);
int y=tree[x].f,z=0;
while(y!=f)
{
z=tree[y].f;
push_down(z);
push_down(y);
push_down(x);
if(z==f)
rotate(x,x==tree[y].r);
else
{
if((x==tree[y].l ^ y==tree[z].l)==0)
{
rotate(y,y==tree[z].r);
rotate(x,x==tree[y].r);
}
else
{
rotate(x,x==tree[y].r);
rotate(x,x==tree[z].r);
}
}
push_up(x);
y=tree[x].f;
}
push_up(x);
if(f==0)
root=x;
}
void insert(int val,int id)
{
tree[++ecnt].val=val;
tree[ecnt].sumval=val;
tree[ecnt].id=id;
tree[ecnt].size=1;
tree[ecnt].l=tree[ecnt].r=tree[ecnt].f=0;
int y=0,x=root;
while(x)
{
y=x;
if(tree[x].id>id)
x=tree[x].l;
else if(tree[x].id<id)
x=tree[x].r;
else
return ;
}
if(y==0)
root=ecnt;
else if(id<tree[y].id)
{
tree[y].l=ecnt;
tree[ecnt].f=y;
}
else
{
tree[y].r=ecnt;
tree[ecnt].f=y;
}
splay(ecnt,0);
}
int get_node(int id)
{
int x=root;
push_down(x);
while(1)
{
if(tree[x].id<id)
x=tree[x].r;
else if(tree[x].id>id)
x=tree[x].l;
else
break;
push_down(x);
}
return x;
}
ll Query(int a,int b)//查询a~b
{
splay(get_node(a-1),0);
splay(get_node(b+1),root);//旋转
return tree[tree[tree[root].r].l].sumval;
}
void add(int a,int b,int x)
{
splay(get_node(a-1),0);
splay(get_node(b+1),root);//旋转
lazy[tree[tree[root].r].l]+=x;
tree[tree[tree[root].r].l].sumval+=tree[tree[tree[root].r].l].size*x;
}
int main()
{
//std::ios::sync_with_stdio(false);
while(~scanf("%d%d",&n,&m))
{
intt();
ll data;
insert(0,0);
for(int i=1;i<=n;++i)
{
scanf("%lld",&data);
insert(data,i);
}
insert(0,n+1);
//show(root);cout<<endl;
//建树完成
char ch[5];
ll a,b,c;
while(m--)
{
scanf("%s",&ch);
if(ch[0]=='Q')
{
scanf("%lld%lld",&a,&b);
printf("%lld\n",Query(a,b));
}
else
{
scanf("%lld%lld%lld",&a,&b,&c);
add(a,b,c);
}
//show(root);cout<<endl;
}
}
}
/*
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
*/
京公网安备 11010502036488号