Splay基本操作:
1.rotate() 旋转操作---包含三种情况
2.splay() 伸展-----一般是旋到根或根的父亲的下面
3.rotate_to() 先找到要伸展的结点，再splay;
4.push_up() 向上维护根的信息
5.push_down()向下下放延迟标记
6.Cut() 删除一个区间
7.insert()插入一个区间
8.Flip()翻转一个区间
9.pred()求结点的前驱
10.succ()求结点的后继
11.dfs()中序遍历---为了输出序列.
12.built()二分建树
13.New_Node()新建结点--如果多个函数要用到则写，否则不用！
poj3468--其它数据结构也可以实现！
//12344261 3468 Accepted 4468K 2907MS C++ 3222B 2013-12-01 11:37:06
#include <iostream>
#include<cstdio>
using namespace std;
#define MAX 100010
#define bint __int64
int N,Q,tot;
int A[MAX];
struct Node
{
int size,vol,add;
bint sum;
Node*d[2];
Node*pre;
}*Null,*root,space[MAX];
void updata(Node*p)
{
p->size=p->d[0]->size+p->d[1]->size+1;
p->sum=p->d[0]->sum+p->d[1]->sum+p->vol;
}
void Push_down(Node*x)
{
if(x==Null) return;
x->vol+=x->add;
x->d[0]->add+=x->add;
x->d[1]->add+=x->add;
if(x->d[0]!=Null)
x->d[0]->sum+=(bint)(x->add)*(x->d[0]->size);
if(x->d[1]!=Null)
x->d[1]->sum+=(bint)(x->add)*(x->d[1]->size);
x->add=0;
}
void Rotate(Node*x,int c)
{
Node*y=x->pre;
Push_down(y),Push_down(x);
y->d[!c]=x->d[c],x->pre=y->pre;
if(x->d[c]!=Null) x->d[c]->pre=y;
if(y->pre!=Null) y->pre->d[y->pre->d[1]==y]=x;
y->pre=x,x->d[c]=y;
if(root==y) root=x;
updata(y);
}
void Splay(Node*x,Node*f)
{
for(Push_down(x);x->pre!=f;)
{
if(x->pre->pre==f)
Rotate(x,x->pre->d[0]==x);
else
{
Node *y=x->pre , *z=y->pre;
if(z->d[0]==y)
if(y->d[0]==x)
Rotate(y,1),Rotate(x,1);
else
Rotate(x,0),Rotate(x,1);
else
if(y->d[1]==x)
Rotate(y,0),Rotate(x,0);
else
Rotate(x,1),Rotate(x,0);
}
}
updata(x);
}
Node* New_Node(int x)
{
Node*p=&space[tot++];
p->d[0]=p->d[1]=p->pre=Null;
p->add=0;
p->size=1;
p->sum=p->vol=x;
return p;
}
Node* Make_Tree(int l,int r,Node* fa)
{
if(l>r) return Null;
int m=(l+r)>>1;
Node*p=New_Node(A[m]);
p->d[0]=Make_Tree(l,m-1,p);
p->d[1]=Make_Tree(m+1,r,p);
p->pre=fa;
updata(p);
return p;
}
void init()
{
tot=0;
Null=New_Node(0);
Null->size=0;
root=New_Node(-1);
root->d[1]=New_Node(-1);
root->d[1]->pre=root;
updata(root);
root->d[1]->d[0]=Make_Tree(1,N,root->d[1]);
}
void Select(int k,Node*f)
{
Node*p=root;
while(true)
{
Push_down(p);
int tem=p->d[0]->size;
if(k==tem+1) break;
if(k <= tem)
p=p->d[0];
else
p=p->d[1],k-=tem+1;
}
Splay(p,f);
}
int main()
{
while(~scanf("%d%d",&N,&Q))
{
for(int i=1;i<=N;i++)
scanf("%d",&A[i]);
init();
char op[2];
for(int i=1;i<=Q;i++)
{
scanf("%s",op);
if(op[0]=='C')
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
Select(a,Null);
Select(b+2,root);
root->d[1]->d[0]->add+=c;
root->d[1]->d[0]->sum+=(bint)c*(root->d[1]->d[0]->size);
}
else
{
int a,b;
scanf("%d%d",&a,&b);
Select(a,Null);
Select(b+2,root);
printf("%I64d\n",root->d[1]->d[0]->sum);
}
}
}
return 0;
}
hdu4441---指定位置插入（最好用splay）
//9740664 2013-12-02 22:21:47 Accepted 4441 1140MS 9464K 3860 B G++
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;
#define Stype(x) (ns[ns[x].f].son[1]==x)
typedef __int64 ll;
const int N = 100005;
int m;int posn[N],posp[N];
struct Splay
{
int nns,begin,end;
struct node{int size,key,f,son[2]; ll sum; bool p;}ns[2*N];
inline int operator[](int x){return ns[x].key;}
inline int NewNode(int x,int f)
{
ns[++nns].key=ns[nns].sum=x;
ns[nns].size=1;
ns[nns].f=f;
ns[nns].p=x>0;
return nns;
}
inline void init()
{
nns=0;
memset(ns,0,sizeof(ns));
begin=ns[0].son[0]=NewNode(0,0);
end=ns[1].son[1]=NewNode(0,1);
Updata(1);
}
inline void Updata(int x)
{
ns[x].sum=ns[ns[x].son[0]].sum+ns[ns[x].son[1]].sum+ns[x].key;
ns[x].size=ns[ns[x].son[0]].size+ns[ns[x].son[1]].size+1;
ns[x].p=ns[x].key>0 || ns[ns[x].son[0]].p || ns[ns[x].son[1]].p;
}
int pred(int x)
{
splay(x);
for(x=ns[x].son[0];ns[x].son[1];x=ns[x].son[1]);
splay(x);return x;
}
int succ(int x)
{
splay(x);
for(x=ns[x].son[1];ns[x].son[0];x=ns[x].son[0]);
splay(x);return x;
}
int ins(int x,int s)
{
//cout<<"asdasda\n";
int p=pred(s);
splay(p),splay(s,p);
x=ns[s].son[0]=NewNode(x,s);
Updata(s),Updata(p);
splay(x);return x;
}
int kth(int k)
{
int x=ns[0].son[0],ls;
while(true)
{
ls=ns[ns[x].son[0]].size;
if(ls+1==k) {splay(x);return x;}
if(ls < k)
x=ns[x].son[1],k-=ls+1;
else
x=ns[x].son[0];
}
}
int F(int x)
{
splay(x);x=ns[x].son[1];
if(!ns[x].p) return 0;
while(true)
{
if(ns[ns[x].son[0]].p) x=ns[x].son[0];
else if(ns[x].key > 0) {splay(x);return x;}
else x=ns[x].son[1];
}
}
void rot(int x)
{
int ST=Stype(x),f=ns[x].f;
ns[ns[f].f].son[Stype(f)]=x;
ns[x].f=ns[f].f;
ns[f].son[ST]=ns[x].son[!ST];
if(ns[x].son[!ST]) ns[ns[x].son[!ST]].f=f;
ns[f].f=x;
ns[x].son[!ST]=f;
Updata(f);
}
void splay(int x,int to=0)
{
while(ns[x].f!=to)
if(ns[ns[x].f].f!=to)
{
if(Stype(x)==Stype(ns[x].f))
rot(ns[x].f),rot(x);
else
rot(x),rot(x);
}
else rot(x);
Updata(x);
}
void Del(int x)
{
int s=succ(x),p=pred(x);
splay(p),splay(s,p);
ns[s].son[0]=0;
Updata(s),Updata(p);
}
ll S(int l,int r)
{
splay(l),splay(r,l);
return ns[ns[r].son[0]].sum;
}
}T;
void run()
{
priority_queue< int, vector<int>, greater<int> > H;
for(int i=1;i<=m;i++) H.push(i);
T.init();
char ch[8];int x,w,w2,key;
for(int i=1;i<=m;i++)
{
scanf("%s%d",ch,&x);
if(ch[0]=='i')
{
key=H.top();H.pop();
posp[key]=w=T.ins(key,T.kth(x+2));
w2=T.F(w);
if(w2)
posn[key]=T.ins(-key,posn[T[w2]]);
else
posn[key]=T.ins(-key,T.end);
}
else if(ch[0]=='r')
{
T.Del(posn[x]); T.Del(posp[x]);
H.push(x);
}
else
printf("%I64d\n", T.S(posp[x], posn[x]));
}
}
int main()
{
int t=0;
while(~scanf("%d",&m))
{
printf("Case #%d:\n", ++t);
run();
}
return 0;
}
hdu3487--区间翻转，切割
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 333333;
#define m_set(ptr,v,type,size) memset(ptr,v,sizeof(type)*size)
#define loop(begin,end) for(int i=begin;i<end;i++)
class SplayTree{
#define l(x) (nod[x].son[0])
#define r(x) (nod[x].son[1])
#define Juge(x) (nod[pre[x]].son[1]==x)
#define mid(x,y) ((x+y)>>1)
public:
int a[MAXN],pre[MAXN];
struct node{int val,rev,sz,son[2];}nod[MAXN];
int root,tot;
void init(){
memset(nod,0,sizeof(nod));
root = tot = 0;
}
void read(int n){
a[1] = a[n+2] = 0;
loop(2,n+2){ a[i] = i-1; }
}
void push_up(int rt){
nod[rt].sz=nod[l(rt)].sz+nod[r(rt)].sz+1;
}
void swap(int &x,int &y){
int tmp = x;
x = y;
y = tmp;
}
void push_down(int rt){
if(nod[rt].rev){
swap(l(rt),r(rt));
if(l(rt)) nod[l(rt)].rev ^= 1;//采用异或 ^=
if(r(rt)) nod[r(rt)].rev ^= 1;
nod[rt].rev = 0;
}
}
void rotate(int x,int f){
/**分三步旋转**/
/**第一步：把x和y的儿子连好**/
int y = pre[x];
nod[y].son[!f]=nod[x].son[f];
if(nod[y].son[!f]) pre[nod[y].son[!f]] = y;
push_up(y);
/**第二步：把x的父亲连好**/
if(pre[y]) nod[pre[y]].son[r(pre[y])==y]=x;
pre[x] = pre[y];
/**第三步：把y的父亲连好**/
nod[x].son[f] = y;
pre[y] = x;
}
void splay(int x,int goal)
{
/**分三种情形的旋转!**/
while(pre[x]!=goal)
{
int y = pre[x], z = pre[pre[x]];
if(z==goal)
{
rotate(x,!Juge(x));
}
else
{
if(Juge(y))
{
if(Juge(x)) rotate(y,0),rotate(x,0);
else rotate(x,1),rotate(x,0);
}
else
{
if(!Juge(x)) rotate(y,1),rotate(x,1);
else rotate(x,0),rotate(x,1);
}
}
}
push_up(x);/**最后在更新x的信息,没必要在rotate里面去更新,它里面只需更新改动的父亲结点信息!**/
if(goal==0) root = x;/**要记得维护一下 root的信息!**/
}
void rotateTo(int k,int goal){
/**先找到第k个位置,然后splay到goal！**/
int x = root;
while(1){
push_down(x);
int tmp = nod[l(x)].sz+1;
if(k==tmp) break;
else if(k<tmp) x = l(x);
else{
k -= tmp;
x = r(x);
}
}
splay(x,goal);
}
void buildTree(int l,int r,int &rt,int f){
/**二分的去建树！**/
if(l>r)return;
int m = mid(l,r);
rt = ++tot;
nod[rt].val=a[m];
pre[rt] = f;
buildTree(l,m-1,l(rt),rt);
buildTree(m+1,r,r(rt),rt);
push_up(rt);/**返回的时候，将根结点信息更新！**/
}
void rangeCut(int l,int r,int goal){
/**先删除一段**/
rotateTo(l-1,0);
rotateTo(r+1,root);
int x = l(r(root));
l(r(root)) = 0;
pre[x] = 0;
push_up(r(root));
push_up(root);
/**后插入一段**/
rotateTo(goal,0);
rotateTo(goal+1,root);
l(r(root)) = x;
pre[x] = r(root);
push_up(r(root));
push_up(root);
}
void rangeFlip(int l,int r){
rotateTo(l-1,0);
rotateTo(r+1,root);
int x = l(r(root));
nod[x].rev^=1;/**延迟标记**/
}
void dfs(int rt,int &size){
if(!rt) return;
push_down(rt);/**遍历使要下放延迟标记，才能得到正确结果!**/
dfs(l(rt),size);
a[size++] = nod[rt].val;
dfs(r(rt),size);
}
/////////////////debug///////////////////////
}spt;
int main(){
int n,m;
while(scanf("%d%d",&n,&m),!(n<0&&m<0)){
spt.init();
spt.read(n);
spt.buildTree(1,n+2,spt.root,0);
char op[5]; int a,b,c;
while(m--){
scanf("%s%d%d",op,&a,&b);
if(op[0]=='C'){
scanf("%d",&c);
spt.rangeCut(a+1,b+1,c+1);
}else{
spt.rangeFlip(a+1,b+1);
}
}
n = 0;
spt.dfs(spt.root,n);
loop(1,n-1){
if(i!=1)printf(" ");
printf("%d",spt.a[i]);
}
printf("\n");
}
return 0;
}
hdu4286--双向链表实现的区间翻转\
TLE 普通的翻转，即每翻转一次就把区间里所有节点都翻转过来！
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 500010
struct Node
{
int pred,last,vol;
}a[maxn];
int l,r,tot,size;
void reverse()
{
for(int i=a[l].last;i!=r;i=a[i].pred) swap(a[i].pred,a[i].last);
a[a[l].last].last=r;
a[a[r].pred].pred=l;
swap(a[l].last,a[r].pred);
}
void Del(char ch)
{
size--;
if(ch=='L')
{
a[a[a[l].last].last].pred=l;
a[l].last=a[a[l].last].last;
}
else
{
a[a[a[r].pred].pred].last=r;
a[r].pred=a[a[r].pred].pred;
}
}
void init(int n)
{
tot=0;size=0;
l=0;r=n+1;
a[l].pred=-1;a[l].last=r;
a[r].pred=l;a[r].last=-1;
}
void Insert(char ch,int vol)
{
a[++tot].vol=vol;size++;
if(ch=='L')
{
a[tot].pred=l;
a[tot].last=a[l].last;
a[a[l].last].pred=tot;
a[l].last=tot;
}
else
{
a[tot].last=r;
a[tot].pred=a[r].pred;
a[a[r].pred].last=tot;
a[r].pred=tot;
}
}
void left(char ch)
{
if(ch=='L') l=a[l].pred;
else r=a[r].pred;
}
void right(char ch)
{
if(ch=='L') l=a[l].last;
else r=a[r].last;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
init(n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[++tot].vol);
a[tot].pred=l;
a[tot].last=a[l].last;
a[l].last=tot;
a[a[tot].last].pred=tot;
l=tot;size++;
}
scanf("%d%d",&l,&r);l--;r++;
int m;
scanf("%d",&m);
while(m--)
{
char op[10];
scanf("%s",op);
if(op[0]=='R') {reverse(); continue;}
else if(op[0]=='D') {scanf(" %c",&op[0]);Del(op[0]);}
else if(op[0]=='I') {int d;scanf(" %c%d",&op[0],&d);Insert(op[0],d);}
else
{
char ch;
scanf(" %c",&ch);
if(strcmp(op,"MoveLeft")==0) left(ch);
else right(ch);
}
}
for(int i=1,k=0;i<=size;i++)
{
k=a[k].last;
if(i==1) printf("%d",a[k].vol);
else printf(" %d",a[k].vol);
}
printf("\n");
}
return 0;
}
只要 在L 的前面设一个 LL 在R后面设一个 RR就可以避免上述的没翻转一次全部结点翻转了！
这样的话，LL就相当于是给 L 一个方向感！ RR也是一样的，只不过它代表R的后.
/*
HDU
G++ 4015ms 11968K
双向链表模拟
注意细节
*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<algorithm>
using namespace std;
const int MAXN=2000000;
struct Node
{
int from;
int to;
int val;
}node[MAXN];
int tol;
int L,R;//两个指针
int LL,RR;//分别是指针L，R的左侧和右侧，由于倒一下可能改变方向，所以记录下方向
int n;
void moveleft_L(void)//左移L指针
{
if(L==0)return;//最左侧了
if(node[L].to==LL)
{
LL=L;
L=node[L].from;
}
else
{
LL=L;
L=node[L].to;
}
}
void moveleft_R()
{
if(RR==0)return;
if(node[RR].to==R)
{
R=RR;
RR=node[RR].from;
}
else
{
R=RR;
RR=node[RR].to;
}
}
void moveright_L()
{
if(LL==n+1)return;
if(L==node[LL].from)
{
L=LL;
LL=node[LL].to;
}
else
{
L=LL;
LL=node[LL].from;
}
}
void moveright_R()
{
if(R==n+1)return;
if(node[R].from==RR)
{
RR=R;
R=node[R].to;
}
else
{
RR=R;
R=node[R].from;
}
}
void insert_L(int v)
{
node[tol].val=v;
node[tol].from=L;
node[tol].to=LL;
if(node[L].to==LL)node[L].to=tol;
else node[L].from=tol;
if(node[LL].from==L)node[LL].from=tol;
else node[LL].to=tol;
LL=tol;
tol++;
}
void insert_R(int v)
{
node[tol].val=v;
node[tol].from=RR;
node[tol].to=R;
if(node[RR].to==R)node[RR].to=tol;
else node[RR].from=tol;
if(node[R].from==RR)node[R].from=tol;
else node[R].to=tol;
RR=tol;
tol++;
}
void del_L()
{
if(LL==n+1)return;
if(L==n+1)return;
int t;
if(node[LL].from==L)t=node[LL].to;
else t=node[LL].from;
if(node[t].from==LL)node[t].from=L;
else node[t].to=L;
if(node[L].to==LL)node[L].to=t;
else node[L].from=t;
LL=t;
}
void del_R()
{
if(RR==0)return;
if(R==0)return;
int t;
if(node[RR].to==R)t=node[RR].from;
else t=node[RR].to;
if(node[t].from==RR)node[t].from=R;
else node[t].to=R;
if(node[R].from==RR)node[R].from=t;
else node[R].to=t;
RR=t;
}
void reverse()
{
if(node[L].to==LL)node[L].to=RR;
else node[L].from=RR;
if(node[LL].from==L)node[LL].from=R;
else node[LL].to=R;
if(node[R].from==RR)node[R].from=LL;
else node[R].to=LL;
if(node[RR].to==R)node[RR].to=L;
else node[RR].from=L;
int temp;
temp=LL;
LL=RR;
RR=temp;
}
void output()
{
int flag=true;
int tt=0;
for(int i=node[0].to;i!=n+1;)
{
if(flag)flag=false;
else printf(" ");
printf("%d",node[i].val);
if(node[i].from==tt)
{
tt=i;
i=node[i].to;
}
else
{
tt=i;
i=node[i].from;
}
}
printf("\n");
}
char str[20];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int m;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&node[i].val);
node[i].from=i-1;
node[i].to=i+1;
}
node[0].to=1;
node[0].from=-1;
node[n+1].from=n;
node[n+1].to=-1;
tol=n+2;//结点数
scanf("%d%d",&LL,&RR);
L=LL-1;
R=RR+1;
scanf("%d",&m);
while(m--)
{
scanf("%s",&str);
if(strcmp(str,"MoveLeft")==0)
{
scanf("%s",&str);
if(str[0]=='L')moveleft_L();
else moveleft_R();
}
else if(strcmp(str,"MoveRight")==0)
{
scanf("%s",&str);
if(str[0]=='L')moveright_L();
else moveright_R();
}
else if(strcmp(str,"Delete")==0)
{
scanf("%s",&str);
if(str[0]=='L')del_L();
else del_R();
}
else if(strcmp(str,"Insert")==0)
{
scanf("%s",&str);
if(str[0]=='L')
{
int v;
scanf("%d",&v);
insert_L(v);
}
else
{
int v;
scanf("%d",&v);
insert_R(v);
}
}
else reverse();
}
output();
}
}