COJ 1002 WZJのデータ構造(二)(splayテンプレート)
37243 ワード
私のLCC、LCT、Splayフォーマットがようやく統一されました.
また.この形式のSplayは標準的なSplayです.(どのように鑑定しますか?Splay関数は変数のnodeだけを伝えたらいいですか?)、劉汝佳白書のSplayは本当に突っ込みたくないです.制限が大きすぎて、勉強しないでください.
はい、修理の数列を書きに行きます...
標準Splayテンプレート:
検索
コピー
また.この形式のSplayは標準的なSplayです.(どのように鑑定しますか?Splay関数は変数のnodeだけを伝えたらいいですか?)、劉汝佳白書のSplayは本当に突っ込みたくないです.制限が大きすぎて、勉強しないでください.
はい、修理の数列を書きに行きます...
標準Splayテンプレート:
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<algorithm>
5 #include<queue>
6 #include<cstring>
7 #define PAU putchar(' ')
8 #define ENT putchar('
')
9 #define CH for(int d=0;d<=1;d++) if(ch[d])
10 using namespace std;
11 const int maxn=100000+10;
12 struct node{
13 node*ch[2],*fa;
14 int x,siz;bool rev;char c;
15 node(){x=0;siz=1;rev=false;}
16 void revt(){swap(ch[0],ch[1]);rev^=1;return;}
17 inline void down(){
18 if(rev){CH{ch[d]->revt();}rev=false;}return;
19 }
20 inline void update(){
21 siz=1;CH{siz+=ch[d]->siz;}return;
22 }
23 }Splay[maxn],*root=&Splay[0];int cnt=0;void print(node*x);
24 inline int parent(node*x,node*&y){return (y=x->fa)?y->ch[1]==x?1:y->ch[0]==x?0:-1:-1;}
25 inline void rotate(node*x){
26 node*y,*z;int d1=parent(x,y),d2=parent(y,z);
27 if(y->ch[d1]=x->ch[d1^1]) y->ch[d1]->fa=y;
28 y->fa=x;x->fa=z;x->ch[d1^1]=y;
29 if(d2!=-1) z->ch[d2]=x;
30 y->update();return;
31 }
32 void pushdown(node*x){
33 static node*s[maxn];int top=0;
34 for(node*y;;x=y){
35 s[top++]=x;y=x->fa;
36 if(!y||(y->ch[0]!=x&&y->ch[1]!=x)) break;
37 } while(top--) s[top]->down();return;
38 }
39 node*splay(node*x){
40 pushdown(x);node*y,*z;int d1,d2;
41 while(true){
42 if((d1=parent(x,y))<0) break;
43 if((d2=parent(y,z))<0){rotate(x);break;}
44 if(d1==d2) rotate(y),rotate(x);
45 else rotate(x),rotate(x);
46 } x->update();return x;
47 }
48 node*find(node*x,int rank){
49 x->down();int kth=1; if(x->ch[0]) kth=x->ch[0]->siz+1;
50 if(kth==rank) return x;
51 if(kth>rank) return find(x->ch[0],rank);
52 else return find(x->ch[1],rank-kth);
53 }
54 void split(node*&x,node*&y,int a){//
55 if(!a){y=x;x=NULL;return;}
56 x=splay(find(x,a));
57 y=x->ch[1];x->ch[1]=NULL;x->update();return;
58 }
59 void split(node*&x,node*&y,node*&z,int a,int b){//
60 split(x,z,b);split(x,y,a-1);
61 return;
62 }
63 void join(node*&x,node*y){
64 if(!x){x=y;return;}
65 if(!y) return;
66 x=splay(find(x,x->siz));
67 x->ch[1]=y;y->fa=x;x->update();return;
68 }
69 void join(node*&x,node*y,node*z){
70 join(y,z);join(x,y);return;
71 }
72 void reverse(int a,int b){
73 node*x,*y;split(root,x,y,a,b);x->revt();join(root,x,y);return;
74 }
75 char s[maxn];
76 void build(node*&x,int L,int R){
77 if(L>R) return;x=&Splay[++cnt];
78 int M=L+R>>1;x->c=s[M];
79 build(x->ch[0],L,M-1);build(x->ch[1],M+1,R);
80 if(x->ch[0]) x->ch[0]->fa=x;
81 if(x->ch[1]) x->ch[1]->fa=x;
82 x->update();return;
83 }
84 inline int read(){
85 int x=0,sig=1;char ch=getchar();
86 while(!isdigit(ch)){if(ch=='-')sig=-1;ch=getchar();}
87 while(isdigit(ch))x=10*x+ch-'0',ch=getchar();
88 return x*sig;
89 }
90 void write(int x){
91 if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;
92 int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;
93 for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;
94 }
95 void printer(node*x){
96 if(!x) return;
97 x->down();
98 printer(x->ch[0]);
99 putchar(x->c);
100 printer(x->ch[1]);
101 return;
102 }
103 void init(){
104 scanf("%s",s);
105 build(root,0,strlen(s)-1);
106 int Q=read(),L,R;
107 while(Q--){L=read();R=read();reverse(L,R);}
108 printer(root);
109 return;
110 }
111 void work(){
112 return;
113 }
114 void print(){
115 return;
116 }
117 int main(){init();work();print();return 0;} 1 #include<cstdio>
2 #include<cctype>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 inline void read(int& x)
7 {
8 x=0; char ch=getchar();int sig=1;
9 while(!isdigit(ch)) {if(ch=='-') sig=-1;ch=getchar();}
10 while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
11 x*=sig;
12 }
13 const int maxn=100010;
14 struct Node
15 {
16 Node* ch[2];
17 int s,flip;
18 char c;
19 int cmp(int k)
20 {
21 if(k==ch[0]->s+1) return -1;
22 return k<=ch[0]->s?0:1;
23 }
24 void maintain(){s=ch[0]->s+ch[1]->s+1;}
25 void pushdown()
26 {
27 if(flip)
28 {
29 ch[0]->flip^=1;ch[1]->flip^=1;
30 swap(ch[0],ch[1]);
31 flip=0;
32 }
33 }
34 }*null=new Node(),nodes[maxn];
35 int tot;
36 void rotate(Node* &o,int d)
37 {
38 Node* k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
39 o->maintain();k->maintain();o=k;
40 }
41 void splay(Node* &o,int k)
42 {
43 o->pushdown();
44 int d=o->cmp(k);
45 if(d) k-=o->ch[0]->s+1;
46 if(d!=-1)
47 {
48 Node* p=o->ch[d];p->pushdown();
49 int d2=p->cmp(k);
50 int k2=d2?k-p->ch[0]->s-1:k;
51 if(d2!=-1)
52 {
53 splay(p->ch[d2],k2);
54 if(d==d2) rotate(o,d^1);
55 else rotate(o->ch[d],d);
56 }
57 rotate(o,d^1);
58 }
59 }
60 void print(Node* &o)
61 {
62 if(o==null) return;
63 o->pushdown();
64 print(o->ch[0]);
65 printf("%c",o->c);
66 print(o->ch[1]);
67 }
68 char s[maxn];
69 void build(Node* &o,int L,int R)
70 {
71 o=null;
72 if(L>R) return;
73 int M=L+R>>1;
74 o=&nodes[tot++];
75 o->c=s[M];o->flip=0;
76 build(o->ch[0],L,M-1);build(o->ch[1],M+1,R);
77 o->maintain();
78 }
79 Node *root,*o,*left,*mid,*right;
80 void merge(Node* &left,Node* &right)
81 {
82 if(left==null) left=right;
83 else
84 {
85 splay(left,left->s);
86 left->ch[1]=right;
87 left->maintain();
88 }
89 }
90 void split(Node* &o,Node* &left,Node* &right,int k)
91 {
92 if(!k) left=null,right=o;
93 else
94 {
95 splay(o,k);
96 left=o;
97 right=left->ch[1];
98 left->ch[1]=null;
99 left->maintain();
100 }
101 }
102 int main()
103 {
104 scanf("%s",s);
105 build(root,0,strlen(s)-1);
106 int Q,L,R;
107 read(Q);
108 while(Q--)
109 {
110 read(L),read(R);
111 split(root,left,o,L-1);
112 split(o,mid,right,R-L+1);
113 mid->flip^=1;
114 merge(left,mid);
115 merge(left,right);
116 root=left;
117 }
118 print(root);
119 return 0;
120 }検索
コピー