点操作：
splay树可以一个一个的插入结点，这样的splay树是有序树，结点权值大于左儿子小于右儿子
这样就是点操作
区间操作：
还有就是可以自己建树，这样的splay树就不是按权值的有序树，它不满足结点权值大于左儿子小于右儿子，，
但是它也是有顺序的，无论怎么伸展，把它的结点中序遍历结果就是原来的数组顺序。
因此自己建树可以操作区间！
点操作模板
// File Name: ACM/bzoj/1208.cpp
// Author: Zlbing
// Created Time: 2013年08月08日 星期四 16时33分53秒 #include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)
const int MAXN=8e4+;
const int mod=;
struct SplayTree {
int sz[MAXN];
int ch[MAXN][];
int pre[MAXN];
int rt,top;
inline void up(int x){
sz[x] = cnt[x] + sz[ ch[x][] ] + sz[ ch[x][] ];
}
inline void Rotate(int x,int f){
int y=pre[x];
ch[y][!f] = ch[x][f];
pre[ ch[x][f] ] = y;
pre[x] = pre[y];
if(pre[x]) ch[ pre[y] ][ ch[pre[y]][] == y ] =x;
ch[x][f] = y;
pre[y] = x;
up(y);
}
inline void Splay(int x,int goal){//将x旋转到goal的下面
while(pre[x] != goal){
if(pre[pre[x]] == goal) Rotate(x , ch[pre[x]][] == x);
else {
int y=pre[x],z=pre[y];
int f = (ch[z][]==y);
if(ch[y][f] == x) Rotate(x,!f),Rotate(x,f);
else Rotate(y,f),Rotate(x,f);
}
}
up(x);
if(goal==) rt=x;
}
inline void RTO(int k,int goal){//将第k位数旋转到goal的下面
int x=rt;
while(sz[ ch[x][] ] != k-) {
if(k < sz[ ch[x][] ]+) x=ch[x][];
else {
k-=(sz[ ch[x][] ]+);
x = ch[x][];
}
}
Splay(x,goal);
}
inline void vist(int x){
if(x){
printf("结点%2d : 左儿子 %2d 右儿子 %2d %2d sz=%d\n",x,ch[x][],ch[x][],val[x],sz[x]);
vist(ch[x][]);
vist(ch[x][]);
}
}
inline void Newnode(int &x,int c){
x=++top;
ch[x][] = ch[x][] = pre[x] = ;
sz[x]=; cnt[x]=;
val[x] = c;
}
inline void init(){
ans=;type=-;
ch[][]=ch[][]=pre[]=sz[]=;
rt=top=; cnt[]=;
Newnode(rt,-INF);
Newnode(ch[rt][],INF);
pre[top]=rt;
sz[rt]=;
}
inline void Insert(int &x,int key,int f){
if(!x) {
Newnode(x,key);
pre[x]=f;
Splay(x,);
return ;
}
if(key==val[x]){
cnt[x]++;
sz[x]++;
return ;
}else if(key<val[x]) {
Insert(ch[x][],key,x);
} else {
Insert(ch[x][],key,x);
}
up(x);
} void Del(){ //删除根结点
int t=rt;
if(ch[rt][]) {
rt=ch[rt][];
RTO(,);
ch[rt][]=ch[t][];
if(ch[rt][]) pre[ch[rt][]]=rt;
}
else rt=ch[rt][];
pre[rt]=;
up(rt);
}
void findpre(int x,int key,int &ans){ //找key前趋
if(!x) return ;
if(val[x] <= key){
ans=x;
findpre(ch[x][],key,ans);
} else
findpre(ch[x][],key,ans);
}
void findsucc(int x,int key,int &ans){ //找key后继
if(!x) return ;
if(val[x]>=key) {
ans=x;
findsucc(ch[x][],key,ans);
} else
findsucc(ch[x][],key,ans);
}
//找第K大数
inline int find_kth(int x,int k){
if(k<sz[ch[x][]]+) {
return find_kth(ch[x][],k);
}else if(k > sz[ ch[x][] ] + cnt[x] )
return find_kth(ch[x][],k-sz[ch[x][]]-cnt[x]);
else{
Splay(x,);
return val[x];
}
}
int cnt[MAXN];
int val[MAXN];
int type;
int ans;
}spt;
int main()
{
int n;
while(~scanf("%d",&n))
{
spt.init();
int a,b;
int ans=;
int type=-;
REP(i,,n)
{
scanf("%d%d",&a,&b);
if(a==type||spt.sz[spt.rt]==)
{
spt.Insert(spt.rt,b,);
type=a;
//spt.vist(spt.rt);
}
else
{
int x,y;
if(spt.sz[spt.rt]==)continue;
spt.findpre(spt.rt,b,x);
spt.findsucc(spt.rt,b,y);
if(abs(spt.val[x]-b)<=abs(spt.val[y]-b))
{
ans+=abs(spt.val[x]-b);
ans%=mod;
spt.Splay(x,);
//spt.vist(spt.rt);
spt.Del();
}
else{
ans+=abs(spt.val[y]-b);
ans%=mod;
spt.Splay(y,);
//spt.vist(spt.rt);
spt.Del();
}
}
}
printf("%d\n",ans);
}
return ;
}
区间操作模板
// File Name: ACM/HDU/3487.cpp
// Author: Zlbing
// Created Time: 2013年08月10日 星期六 21时35分28秒 #include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)
#define L ch[x][0]
#define R ch[x][1]
#define KT (ch[ ch[rt][1] ][0])
const int MAXN = 3e5+;
struct SplayTree {
int sz[MAXN];
int ch[MAXN][];
int pre[MAXN];
int rt,top;
inline void down(int x){
if(flip[x]) {
flip[ L ] ^= ;
flip[ R ] ^= ;
swap(L,R);
flip[x]=;
}
}
inline void up(int x){
sz[x]=+sz[ L ] + sz[ R ];
}
inline void Rotate(int x,int f){
int y=pre[x];
down(y);
down(x);
ch[y][!f] = ch[x][f];
pre[ ch[x][f] ] = y;
pre[x] = pre[y];
if(pre[x]) ch[ pre[y] ][ ch[pre[y]][] == y ] =x;
ch[x][f] = y;
pre[y] = x;
up(y);
}
inline void Splay(int x,int goal){//将x旋转到goal的下面
down(x);////防止pre[x]就是目标点，下面的循环就进不去了，x的信息就传不下去了
while(pre[x] != goal){
down(pre[pre[x]]); down(pre[x]);down(x);//在旋转之前需要先下传标记，因为节点的位置可能会发生改变
if(pre[pre[x]] == goal) Rotate(x , ch[pre[x]][] == x);
else {
int y=pre[x],z=pre[y];
int f = (ch[z][]==y);
if(ch[y][f] == x) Rotate(x,!f),Rotate(x,f);
else Rotate(y,f),Rotate(x,f);
}
}
up(x);
if(goal==) rt=x;
}
inline void RTO(int k,int goal){//将第k位数旋转到goal的下面
int x=rt;
down(x);
while(sz[ L ]+ != k) {
if(k < sz[ L ] + ) x=L;
else {
k-=(sz[ L ]+);
x = R;
}
down(x);
}
Splay(x,goal);
}
void vist(int x){
if(x){
printf("结点%2d : 左儿子 %2d 右儿子 %2d %2d flip:%d\n",x,L,R,val[x],flip[x]);
vist(L);
vist(R);
}
}
void Newnode(int &x,int c,int f){
x=++top;flip[x]=;
L = R = ; pre[x] = f;
sz[x]=; val[x]=c;
}
inline void build(int &x,int l,int r,int f){
if(l>r) return ;
int m=(l+r)>>;
Newnode(x,m,f);
build(L , l , m- , x);
build(R , m+ , r , x);
pre[x]=f;
up(x);
} inline void init(int n){
ch[][]=ch[][]=pre[]=sz[]=;
rt=top=; flip[]=; val[]=;
Newnode(rt,-,);
Newnode(ch[rt][],-,rt);
sz[rt]=;
build(KT,,n,ch[rt][]);
}
//删除根结点
void Del(){
int t=rt;
if(ch[rt][]) {
rt=ch[rt][];
RTO(,);
ch[rt][]=ch[t][];
if(ch[rt][]) pre[ch[rt][]]=rt;
}
else rt=ch[rt][];
pre[rt]=;
up(rt);
}
//把[a,b]放在c的后面
void solve1(int a,int b,int c)
{
RTO(a,);
RTO(b+,rt);
int tmp=KT;
KT=;
up(ch[rt][]);
up(rt); RTO(c+,);
RTO(c+,rt);
KT=tmp;
pre[tmp]=ch[rt][];
up(ch[rt][]);
up(rt);
}
//翻转[a,b]
void solve2(int a,int b)
{
RTO(a,);
RTO(b+,rt);
flip[KT]^=;
}
void print(int x)
{
if(x)
{
down(x);
print(L);
if(val[x]!=-)
{
if(flag)printf(" ");
flag=;
printf("%d",val[x]);
}
print(R);
}
}
void out()
{
flag=;
print(rt);
printf("\n");
}
int flip[MAXN];
int val[MAXN];
int flag;
}spt; int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
if(n==-)break;
char op[];
int a,b,c;
spt.init(n);
REP(i,,m)
{
scanf("%s",op);
if(op[]=='C')
{
scanf("%d%d%d",&a,&b,&c);
spt.solve1(a,b,c);
}
else
{
scanf("%d%d",&a,&b);
spt.solve2(a,b);
} }
spt.out();
}
return ;
}