以此文纪念人生首次竞赛大选
这里主要讲一讲splay的区间操作，我讲的是指针实现，程序的效率可能比较低，更偏重代码的可读可写性，语言风格不是很优美有效，不喜勿喷
零、初始化结构体
1）这里主要是初始化结构体，记得先生成一个null节点指针，代表一切未使用的、未开发的节点，root也先赋值为null
2）结构体成员：有几个指针，如父亲（没有也可以，只不过令splay失去一些平衡树的功能），左右儿子，这里用数组记录，下标为0,1，方便我们操作
有几个需要维护的域，如size，子树和根的大小（包括重复节点），mul，重复节点的计数器，rev，区间翻转标记，一层一层地传，addnum，区间加的标记，cov，区间覆盖标记
3）结构体函数：可以自己写一个构造函数，可以声明后在结构体外写，就可以用null指针了，但最好是在结构体外写一个newnode，这样更清晰且更灵活
4）下传函数（relax/pushdown）：
DEBUG：这里注意每次下传rev时，要马上实现交换左右儿子
DEBUG：这里注意所有的，如max域和sum域也要进行区间加操作
主要实现了区间加、区间覆盖、区间翻转的标记的下传
DEBUG：记得从上到下pushdown
5）更新函数（pushup/update）：
根据需要看max域从儿子传上来挑最大，size域加儿子的size和自己的mul，不考虑重复时就用1代替
DEBUG：记得从下到上pushup
一、插入/构造
DEBUG：一下所有的涉及改动的操作记得用址传，不然会出大事哦
1）区间插入，先说进阶的，我们直接对构造一棵平衡树后，将所需区间伸展至根节点右儿子的左儿子处，将构造号的树塞到那里
DEBUG：这里注意塞完树以后记得更新根节点右儿子和根节点的维护域
2）单点插入，和区间一样，伸展所需位置，插入即可
DEBUG：一样滴，这里注意塞完树以后记得更新根节点右儿子和根节点的维护域
（似乎最后将插入的区间做一次splay可以提高效率）
二、删除
主要讲讲区间吧，先把区间伸展到指定位置，我是用递归实现整颗子树的删除的，先递归非空左右儿子，后用系统关键字delete删除当前指针
DEBUG：这里一样要更新有关节点，即pushup
三、旋转
这就不需要多说，平衡树的基础知识
我的函数是指定当前节点，将其对父亲旋转
DEBUG：注意下操作顺序
先提取出父亲的指针，再把当前节点接到父亲的位置
此后把当前和节点异侧的儿子接到父亲连当前节点的位置
之后把父亲接到这个儿子的位置
记得更新一下
四、splay函数/伸展操作
简化一下，主要分了三种情况
第一，当前节点的爷爷是目标节点，直接旋转当前节点
否则
第二，当前节点和父亲不在同侧，旋转当前节点两次
第三，当前节点和父亲在同侧，就先旋转父亲，再旋转当前节点
DEBUG：在函数结尾记得对当前节点进行更新操作，因为旋转函数的更新可能不完全
五、求第k个
这个没什么好说的，我是用循环实现的，非递归
可能此后还有一些进阶操作，这里就不提及了，那不是总结可以穷尽的
最后放个板
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mid ((x>>1)+(y>>1)+(x&y&1))
using namespace std;
const int N = 1e4+;
const int inf = ~0U>>;
struct nt{
nt*ch[],*p; int k,size; int add;bool rev; bool d(){
return this==p->ch[];
} void setc(nt*c,int d){
ch[d]=c;
c->p=this;
} void addIt(int ad){
k+=ad;
add+=ad;
} void revIt(){
rev^=;
swap(ch[],ch[]);
} void pu(){
size=+ch[]->size+ch[]->size;
} void relax(){
if(rev)
ch[]->revIt(),
ch[]->revIt(),
rev=;
if(add)
ch[]->addIt(add),
ch[]->addIt(add),
add=;
}
}; nt*null=new nt();
nt*root=null;
int a[N]; nt*make(nt*p,int k){
nt*now=new nt();
now->size=;
now->k=k;
now->p=p;
now->ch[]=now->ch[]=null;
return now;
} void rot(nt*&o){
nt*p=o->p;
p->relax();
o->relax();
bool d=o->d();
p->p->setc(o,p->d());
p->setc(o->ch[!d],d);
o->setc(p,!d);
p->pu();o->pu();
if(p==root)root=o;
} void splay(nt*o,nt*p){
while(o->p!=p)
if(o->p->p==p)
rot(o);
else
o->d()^o->p->d()?(rot(o),rot(o)):(rot(o->p),rot(o));
o->pu();
} nt*build(int x,int y){
if(x>y)return null;
nt*o=make(o,a[mid]);
o->setc(build(x,mid-),);
o->setc(build(mid+,y),);
o->pu();
return o;
} void del(nt*&o){
if(o->ch[]!=null)del(o->ch[]);
if(o->ch[]!=null)del(o->ch[]);
delete o;
} nt*kth(int k){
for(nt*o;;){
o->relax();
if(k<=o->ch[]->size)
o=o->ch[];
else{
k-=o->ch[]->size+;
if(!k)return o;
o=o->ch[];
}
}
} int main(){
int n;
/*
*a=read(1~n)
*/
root=build(,n+);
root->p=null;
/*
insert l,r?
*a=read(1~r)
splay(kth(l+1),null)
splay(kth(l+2),root)
root->ch[1]->setc(build(1,r),0)
root->ch[1]->pu()
root->pu()
*/
return ;
}
完结，撒花~~~