COJ 1002 WZJ的数据结构（二）（splay模板）

我的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 ;

 }

搜索

复制