hihocoder 1677 翻转字符串 splay

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

给定一个字符串S，小Hi希望对S进行K次翻转操作。

每次翻转小Hi会指定两个整数Li和Ri，表示要将S[Li..Ri]进行翻转。（S下标从0开始，即S[0]是第一个字母)

例如对于S="abcdef"，翻转S[2..3] 得到S="abdcef"；再翻转S[0..5]得到S="fecdba"。

输入

第一行包含一个由小写字母组成的字符串S。

第二行包含一个整数K。

以下K行每行包含两个整数Li和Ri。

对于50%的数据，1 ≤ |S| ≤ 1000

对于100%的数据，1 ≤ |S| ≤ 100000, 1 ≤ K ≤ 100000, 0 ≤ Li ≤ Ri < |S|

输出

输出经过K次翻转后的字符串S

样例输入

abcdef  
2  
2 3  
0 5

样例输出

fecdba

大意：给一个字符串，然后有K个区间翻转操作，求所有操作完成后的字符串。

题解：

splay的经典应用：区间操作（翻转、删除、插入）。

splay备忘：（只是备忘）

首先是rotate操作——不改变树中序遍历。这是splay能够转来转去的基础。relink重新连边的顺序不能变。

然后是splay（x,y）操作——将x旋转到y的子节点位置。注意：两个push_up的位置很重要，不能随意push_up正在向上旋的点。

在splay的过程中分两种情况

（1）x、x->father、x->father->father 在一条线上（x和x->father分别为x->father和x->father->father 的同侧子节点）

这时先rotate(x->father)再rotate(x)，虽然rotate()两次，但是x只上升一层(深度减少1)，这样做是值得的，因为当三个点在一条线上时，splay有些不平衡，而如此rotate两次后splay变得平衡，这是保证splay不退化的关键操作。

（2）不在一条线上

这就没什么顾虑了，直接将rotate(x)两次就行了，x上升两层。

insert(root,val)——增加新节点时要把它旋转到根节点，这是为了保证splay的平衡性。

各种查找（查找第K大，查找值为val的节点，询问值为val的排名等等）—— 二叉查找树基本操作。

区间操作——全部转化为删除排名在[L,R]区间的元素。

将排名L-1的元素旋至根节点，将排名R+1的元素旋至根节点的右子节点。这样，待操作就都在排名R+1的元素的左子树了。

区间操作要像线段树一样把tag push_down。

下面贴上代码（很多操作不全，懒得写了）

  1 /*
  2 Welcome Hacking
  3 Wish You High Rating
  4 */
  5 #include<iostream>
  6 #include<cstdio>
  7 #include<cstring>
  8 #include<ctime>
  9 #include<cstdlib>
 10 #include<algorithm>
 11 #include<cmath>
 12 #include<string>
 13 using namespace std;
 14 int read(){
 15     int xx=0,ff=1;char ch=getchar();
 16     while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
 17     while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
 18     return xx*ff;
 19 }
 20 const int maxn=100010;
 21 int N,Q;
 22 char str[maxn];
 23 struct SPLAY{
 24     int ch[2],v,fa,sum;
 25     bool rev;
 26     void clear()
 27     {ch[0]=0,ch[1]=0,v=0,fa=0,rev=0,sum=0;}
 28     void init(int pos)
 29     {clear();v=pos;sum=1;}
 30 }T[maxn];
 31 int cnt,root;
 32 void push_up(const int&x)
 33 {T[x].sum=T[T[x].ch[0]].sum+T[T[x].ch[1]].sum+1;}
 34 void push_down(const int&x){
 35     if(!T[x].rev)
 36         return;
 37     swap(T[x].ch[0],T[x].ch[1]);
 38     T[T[x].ch[0]].rev^=1;
 39     T[T[x].ch[1]].rev^=1;
 40     T[x].rev=0;
 41 }
 42 inline bool which(int x)
 43 {return T[T[x].fa].ch[1]==x;}
 44 inline void relink(int x,int y,int tt)
 45 {T[x].ch[tt]=y,T[y].fa=x;}
 46 void rotate(int x){
 47     int y=T[x].fa,ffa=T[y].fa,tt=which(x),ttt=which(y);
 48     relink(ffa,x,ttt);
 49     relink(y,T[x].ch[tt^1],tt);
 50     relink(x,y,tt^1);
 51     push_up(y);
 52 }
 53 void splay(int x,int tar){
 54     push_down(x);
 55     while(T[x].fa!=tar){
 56         if(T[T[x].fa].fa==tar){
 57             rotate(x);
 58             break;
 59         }
 60         else if(which(x)==which(T[x].fa)){
 61             rotate(T[x].fa);
 62             rotate(x);
 63         }
 64         else{
 65             rotate(x);
 66             rotate(x);
 67         }
 68     }
 69     push_up(x);
 70     if(!tar)
 71         root=x;
 72 }
 73 int build(int L,int R){
 74     if(L>R)
 75         return 0;
 76     int mid=(L+R)>>1;
 77     int x=++cnt;
 78     if(!root)root=x;
 79     T[x].init(mid);
 80     T[x].ch[0]=build(L,mid-1);
 81     T[x].ch[1]=build(mid+1,R);
 82     if(T[x].ch[0])
 83         T[T[x].ch[0]].fa=x;
 84     if(T[x].ch[1])
 85         T[T[x].ch[1]].fa=x;
 86     push_up(x);
 87     return x;
 88 }
 89 void trav(int x){
 90     if(!x)
 91         return;
 92     push_down(x);
 93     trav(T[x].ch[0]);
 94     if(T[x].v>=1&&T[x].v<=N)
 95         printf("%c",str[T[x].v]);
 96     trav(T[x].ch[1]);
 97 }
 98 int find_element(int x,int v){
 99     push_down(x);
100     if(v==T[x].v)
101         return x;
102     if(v<T[x].v)
103         return find_element(T[x].ch[0],v);
104     return find_element(T[x].ch[1],v);
105 }
106 int find_rank(int x,int rk){
107     push_down(x);
108     if(T[T[x].ch[0]].sum>=rk)
109         return find_rank(T[x].ch[0],rk);
110     if(T[T[x].ch[0]].sum+1==rk)
111         return x;
112     return find_rank(T[x].ch[1],rk-T[T[x].ch[0]].sum-1);
113 }
114 void rever(int L,int R){
115     int x=find_rank(root,L),y=find_rank(root,R+2);//多插入了边界元素，因此区间有平移
116     splay(x,0);
117     splay(y,root);
118     T[T[y].ch[0]].rev^=1;
119 }
120 int get_rank(int x,int v){
121     if(v==T[x].v)
122         return 1;
123     if(v<T[x].v)
124         return get_rank(T[x].L,v);
125     return get_rank(T[x].R,v)+T[T[x].L].sum+1;
126 }
127 void ins(int &x,int v){
128     if(!x){
129         x=++cnt;
130         T[x].init(v);
131         splay(x,0);
132         return;
133     }
134     if(v<T[x].v)
135         insert(T[x].ch[0],v);
136     else
137         insert(T[x].ch[1],v);
138 }
139 void del_value(int v){
140     int temp=get_rank(root,v);
141     splay(temp-1,0);
142     splay(temp+1,root);
143     T[T[temp].ch[0]].clear();
144     T[temp].ch[0]=0;
145 }
146 void del_rank(int L,int R){
147     int x=find_rank(L),y=find_rank(R+2);
148     splay(x,0);
149     splay(y,root);
150     T[T[y].ch[0]].clear();
151     T[y].ch[0]=0;
152 }
153 int main(){
154     //freopen("in.txt","r",stdin);
155     //freopen("out.txt","w",stdout);
156     gets(str+1);
157     N=strlen(str+1);
158     build(0,N+1);
159     Q=read();
160     while(Q--){
161         int t1=read()+1,t2=read()+1;
162         rever(t1,t2);
163     }
164     trav(root);
165     return 0;
166 }

View Code

ins函数有问题

跳过即可