维护一个01序列，一共四种操作：
1.插入一个数
2.删除一个数
3.反转一个区间
4.查询两个后缀的LCP
用Splay或者Treap都可以做，维护哈希值，二分求LCP即可。
注意反转序列的时候序列的哈希值也会改变，因此需要维护正反两个哈希值，在交换左右儿子的时候顺便交换两个哈希值即可。
还有就是打标记的同时也要进行反转，不要等pushdown的时候再反转
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned long long ll; 4 const int N=4e5+10,M=1e9+7; 5 int n,m,ch[N][2],siz[N],re[N],val[N],tot,rt; 6 ll h1[N],h2[N],pm[N]; 7 char s[N]; 8 #define l(u) ch[u][0] 9 #define r(u) ch[u][1] 10 #define mid ((l+r)>>1) 11 int newnode(int x) {int u=++tot; l(u)=r(u)=re[u]=0,siz[u]=1,val[u]=h1[u]=h2[u]=x; return u;} 12 void pu(int u) { 13 siz[u]=siz[l(u)]+siz[r(u)]+1; 14 h1[u]=h1[l(u)]*pm[siz[r(u)]+1]+val[u]*pm[siz[r(u)]]+h1[r(u)]; 15 h2[u]=h2[r(u)]*pm[siz[l(u)]+1]+val[u]*pm[siz[l(u)]]+h2[l(u)]; 16 } 17 void rv(int u) {swap(l(u),r(u)),swap(h1[u],h2[u]),re[u]^=1;} 18 void pd(int u) {if(re[u])re[u]=0,rv(l(u)),rv(r(u));} 19 void sp(int w,int k,int& u,int& v) { 20 if(!w) {u=v=0; return;} 21 pd(w); 22 if(k>=siz[l(w)]+1)u=w,sp(r(w),k-(siz[l(w)]+1),r(u),v),pu(u); 23 else v=w,sp(l(w),k,u,l(v)),pu(v); 24 } 25 void mg(int& w,int u,int v) { 26 if(!u||!v) {w=u|v; return;} 27 if(rand()%(siz[u]+siz[v])<siz[u])pd(u),w=u,mg(r(w),r(u),v); 28 else pd(v),w=v,mg(l(w),u,l(v)); 29 pu(w); 30 } 31 void ins(int& u,int p,int x) { 32 int L,R; 33 sp(u,p,L,R),mg(L,L,newnode(x)),mg(u,L,R); 34 } 35 void del(int& u,int p) { 36 int L,M,R; 37 sp(u,p,L,R),sp(L,p-1,L,M),mg(u,L,R); 38 } 39 void rev(int& u,int l,int r) { 40 int L,M,R; 41 sp(u,r,L,R),sp(L,l-1,L,M); 42 rv(M); 43 mg(L,L,M),mg(u,L,R); 44 } 45 ll H(int& u,int l,int r) { 46 int L,M,R; 47 sp(u,r,L,R),sp(L,l-1,L,M); 48 ll ret=h1[M]; 49 mg(L,L,M),mg(u,L,R); 50 return ret; 51 } 52 int lcp(int& u,int L,int R) { 53 int l=0,r=n-R+1,ret; 54 while(l<=r) { 55 if(H(u,L,L+mid-1)==H(u,R,R+mid-1))ret=mid,l=mid+1; 56 else r=mid-1; 57 } 58 return ret; 59 } 60 void build(int& u,int l=1,int r=n) { 61 if(l>r)return; 62 u=newnode(s[mid-1]-'0'+1); 63 build(l(u),l,mid-1),build(r(u),mid+1,r),pu(u); 64 } 65 int main() { 66 srand(time(0)); 67 pm[0]=1; 68 for(int i=1; i<N; ++i)pm[i]=pm[i-1]*M; 69 while(scanf("%d%d",&n,&m)==2) { 70 scanf("%s",s); 71 tot=0,build(rt); 72 while(m--) { 73 int f,a,b; 74 scanf("%d%d",&f,&a); 75 if(f!=2)scanf("%d",&b); 76 if(f==1)ins(rt,a,b+1),n++; 77 else if(f==2)del(rt,a),n--; 78 else if(f==3)rev(rt,a,b); 79 else if(f==4)printf("%d ",lcp(rt,a,b)); 80 } 81 } 82 return 0; 83 }