我的LCC，LCT，Splay格式终于统一起来了。。。
另外。。这个形式的Splay是标准的Splay（怎么鉴别呢？看Splay函数是否只传了一个变量node就行），刘汝佳小白书的Splay写的真是不想吐槽了，局限性太大，别学。。。
好了我要去写维修数列了。。。。。
标准Splay模板：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
#define CH for(int d=0;d<=1;d++) if(ch[d])
using namespace std;
const int maxn=+;
struct node{
node*ch[],*fa;
int x,siz;bool rev;char c;
node(){x=;siz=;rev=false;}
void revt(){swap(ch[],ch[]);rev^=;return;}
inline void down(){
if(rev){CH{ch[d]->revt();}rev=false;}return;
}
inline void update(){
siz=;CH{siz+=ch[d]->siz;}return;
}
}Splay[maxn],*root=&Splay[];int cnt=;void print(node*x);
inline int parent(node*x,node*&y){return (y=x->fa)?y->ch[]==x?:y->ch[]==x?:-:-;}
inline void rotate(node*x){
node*y,*z;int d1=parent(x,y),d2=parent(y,z);
if(y->ch[d1]=x->ch[d1^]) y->ch[d1]->fa=y;
y->fa=x;x->fa=z;x->ch[d1^]=y;
if(d2!=-) z->ch[d2]=x;
y->update();return;
}
void pushdown(node*x){
static node*s[maxn];int top=;
for(node*y;;x=y){
s[top++]=x;y=x->fa;
if(!y||(y->ch[]!=x&&y->ch[]!=x)) break;
} while(top--) s[top]->down();return;
}
node*splay(node*x){
pushdown(x);node*y,*z;int d1,d2;
while(true){
if((d1=parent(x,y))<) break;
if((d2=parent(y,z))<){rotate(x);break;}
if(d1==d2) rotate(y),rotate(x);
else rotate(x),rotate(x);
} x->update();return x;
}
node*find(node*x,int rank){
x->down();int kth=; if(x->ch[]) kth=x->ch[]->siz+;
if(kth==rank) return x;
if(kth>rank) return find(x->ch[],rank);
else return find(x->ch[],rank-kth);
}
void split(node*&x,node*&y,int a){//
if(!a){y=x;x=NULL;return;}
x=splay(find(x,a));
y=x->ch[];x->ch[]=NULL;x->update();return;
}
void split(node*&x,node*&y,node*&z,int a,int b){//
split(x,z,b);split(x,y,a-);
return;
}
void join(node*&x,node*y){
if(!x){x=y;return;}
if(!y) return;
x=splay(find(x,x->siz));
x->ch[]=y;y->fa=x;x->update();return;
}
void join(node*&x,node*y,node*z){
join(y,z);join(x,y);return;
}
void reverse(int a,int b){
node*x,*y;split(root,x,y,a,b);x->revt();join(root,x,y);return;
}
char s[maxn];
void build(node*&x,int L,int R){
if(L>R) return;x=&Splay[++cnt];
int M=L+R>>;x->c=s[M];
build(x->ch[],L,M-);build(x->ch[],M+,R);
if(x->ch[]) x->ch[]->fa=x;
if(x->ch[]) x->ch[]->fa=x;
x->update();return;
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*sig;
}
void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
void printer(node*x){
if(!x) return;
x->down();
printer(x->ch[]);
putchar(x->c);
printer(x->ch[]);
return;
}
void init(){
scanf("%s",s);
build(root,,strlen(s)-);
int Q=read(),L,R;
while(Q--){L=read();R=read();reverse(L,R);}
printer(root);
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}
刘汝佳的Splay跑得虽然快但局限性太大：
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
inline void read(int& x)
{
x=; char ch=getchar();int sig=;
while(!isdigit(ch)) {if(ch=='-') sig=-;ch=getchar();}
while(isdigit(ch)) x=x*+ch-'',ch=getchar();
x*=sig;
}
const int maxn=;
struct Node
{
Node* ch[];
int s,flip;
char c;
int cmp(int k)
{
if(k==ch[]->s+) return -;
return k<=ch[]->s?:;
}
void maintain(){s=ch[]->s+ch[]->s+;}
void pushdown()
{
if(flip)
{
ch[]->flip^=;ch[]->flip^=;
swap(ch[],ch[]);
flip=;
}
}
}*null=new Node(),nodes[maxn];
int tot;
void rotate(Node* &o,int d)
{
Node* k=o->ch[d^];o->ch[d^]=k->ch[d];k->ch[d]=o;
o->maintain();k->maintain();o=k;
}
void splay(Node* &o,int k)
{
o->pushdown();
int d=o->cmp(k);
if(d) k-=o->ch[]->s+;
if(d!=-)
{
Node* p=o->ch[d];p->pushdown();
int d2=p->cmp(k);
int k2=d2?k-p->ch[]->s-:k;
if(d2!=-)
{
splay(p->ch[d2],k2);
if(d==d2) rotate(o,d^);
else rotate(o->ch[d],d);
}
rotate(o,d^);
}
}
void print(Node* &o)
{
if(o==null) return;
o->pushdown();
print(o->ch[]);
printf("%c",o->c);
print(o->ch[]);
}
char s[maxn];
void build(Node* &o,int L,int R)
{
o=null;
if(L>R) return;
int M=L+R>>;
o=&nodes[tot++];
o->c=s[M];o->flip=;
build(o->ch[],L,M-);build(o->ch[],M+,R);
o->maintain();
}
Node *root,*o,*left,*mid,*right;
void merge(Node* &left,Node* &right)
{
if(left==null) left=right;
else
{
splay(left,left->s);
left->ch[]=right;
left->maintain();
}
}
void split(Node* &o,Node* &left,Node* &right,int k)
{
if(!k) left=null,right=o;
else
{
splay(o,k);
left=o;
right=left->ch[];
left->ch[]=null;
left->maintain();
}
}
int main()
{
scanf("%s",s);
build(root,,strlen(s)-);
int Q,L,R;
read(Q);
while(Q--)
{
read(L),read(R);
split(root,left,o,L-);
split(o,mid,right,R-L+);
mid->flip^=;
merge(left,mid);
merge(left,right);
root=left;
}
print(root);
return ;
}
搜索
复制