这题貌似全网都是Splay的题解，其实FHQ_Treap当然也是可以做的，这里为暴力非旋Treap党上一份代码。
题目大意就是先给你一个字符串，然后让你维护一些操作：
- (p c)：在第(p)个位置后插入字符(c)
- (p) ：删除第(p)个字符
- (p1 p2)：翻转第(p1)个字符到第(p2)个字符
- (p1 p2)：询问从第(p1)个字符开始的后缀和从第(p2)个字符开始的后缀的LCP
看到LCP，第一眼想到什么？SA,SAM？
但是这两个算法都有一个致命伤——不支持修改，况且这里还有鬼畜的翻转操作。
但是如果只看(1,2,3)操作我们发现其实就是一个序列维护，我们可以用平衡树来维护。
所以大致思路有了，但是有什么东西可以维护序列的值还支持快速修改呢？
很简单，就是Hash！而且Hash求LCP在静态问题不想写SA,SAM时（一般都是写挂了吧）也常常用来得到比暴力优秀的(O(nlog n))复杂度（一般出题人不卡的话都可以过）
所以我们对于平衡树的每一个节点维护左右儿子的(size)和正（从前往后）的(hash)值以及反（从后往前）的(hash)值，然后pushup的时候合并一下即可。
至于为什么要维护反的，这样就可以(O(1))翻转了啊！
询问的时候二分LCP的长度，用Hash值判断即可。复杂度(O(nlog^2 n))
CODE
#include<cstdio>
#include<cctype>
#define RI register int
using namespace std;
typedef unsigned long long ull;
const int N=400005;
const ull seed=233;
int n,m,opt,x,y; ull pw[N];
class FileInputOutput
{
private:
#define S 1<<21
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
#define pc(ch) (Ftop<S?Fout[Ftop++]=ch:(fwrite(Fout,1,S,stdout),Fout[(Ftop=0)++]=ch))
char Fin[S],Fout[S],*A,*B; int Ftop,pt[15];
public:
inline void gd(int &x)
{
char ch; while (!isdigit(ch=tc())); x=ch&15;
}
inline bool read(int &x)
{
x=0; char ch; while (!isdigit(ch=tc())) if (ch==EOF) return 0;
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc())); return 1;
}
inline void write(int x)
{
if (!x) return (void)(pc('0'),pc('
')); RI ptop=0;
while (x) pt[++ptop]=x%10,x/=10; while (ptop) pc(pt[ptop--]+48); pc('
');
}
inline void Fend(void)
{
fwrite(Fout,1,Ftop,stdout);
}
#undef S
#undef tc
#undef pc
}F;
class FHQ_Treap
{
private:
struct treap
{
int ch[2],size,rev,dat,val; ull h,rh;
treap(int Lc=0,int Rc=0,int Size=0,int Val=0,int Dat=0)
{
ch[0]=Lc; ch[1]=Rc; size=Size; h=rh=val=Val; dat=Dat;
}
}node[N]; int tot,seed;
#define lc(x) node[x].ch[0]
#define rc(x) node[x].ch[1]
public:
int rt;
inline int rand(void)
{
return seed=(int)seed*482711LL%2147483647;
}
inline int create(int val)
{
node[++tot]=treap(0,0,1,val,rand()); return tot;
}
inline void swap(int &x,int &y)
{
int t=x; x=y; y=t;
}
inline void swap(ull &x,ull &y)
{
ull t=x; x=y; y=t;
}
inline void pushup(int now)
{
treap lson=node[lc(now)],rson=node[rc(now)]; node[now].size=lson.size+rson.size+1;
node[now].h=1ull*rson.h*pw[lson.size+1]+1ull*node[now].val*pw[lson.size]+lson.h;
node[now].rh=1ull*lson.rh*pw[rson.size+1]+1ull*node[now].val*pw[rson.size]+rson.rh;
}
inline void pushdown(int now)
{
if (!now||!node[now].rev) return; if (lc(now)) flip(lc(now)); if (rc(now)) flip(rc(now)); node[now].rev=0;
}
inline void flip(int now)
{
if (!now) return; node[now].rev^=1; swap(node[now].h,node[now].rh); swap(lc(now),rc(now));
}
inline void merge(int &now,int x,int y)
{
if (!x||!y) return (void)(now=x+y); if (node[x].dat>node[y].dat)
pushdown(x),now=x,merge(rc(now),rc(x),y),pushup(x); else
pushdown(y),now=y,merge(lc(now),x,lc(y)),pushup(y);
}
inline void split(int now,int &x,int &y,int rk)
{
if (!now) return (void)(x=y=0); pushdown(now); if (node[lc(now)].size<rk)
x=now,split(rc(now),rc(x),y,rk-node[lc(now)].size-1); else
y=now,split(lc(now),x,lc(y),rk); pushup(now);
}
public:
inline void clear(void)
{
rt=tot=0; seed=233;
}
inline void insert(int rk,int val)
{
int x=0,y=0,z=create(val);
split(rt,x,y,rk-1);
merge(x,x,z); merge(rt,x,y);
}
inline void remove(int rk)
{
int x=0,y=0,z=0; split(rt,x,y,rk-1);
split(y,y,z,1); merge(rt,x,z);
}
inline void reverse(int l,int r)
{
int x=0,y=0,z=0; split(rt,x,y,l-1); split(y,y,z,r-l+1);
flip(y); merge(y,y,z); merge(rt,x,y);
}
inline ull gethash(int x)
{
return node[x].rev?node[x].rh:node[x].h;
}
inline int getsize(int x)
{
return node[x].size;
}
#undef lc
#undef rc
}T;
inline bool check(int a,int b,int com)
{
int x=0,y=0,z=0; ull h1,h2;
T.split(T.rt,x,y,a-1); if (T.getsize(y)<com) return T.merge(T.rt,x,y),0;
T.split(y,y,z,com); h1=T.gethash(y); T.merge(y,y,z); T.merge(T.rt,x,y);
T.split(T.rt,x,y,b-1); if (T.getsize(y)<com) return T.merge(T.rt,x,y),0;
T.split(y,y,z,com); h2=T.gethash(y); T.merge(y,y,z); T.merge(T.rt,x,y);
return h1==h2;
}
inline int LCP(int x,int y)
{
int l=1,r=T.getsize(T.rt)-1,res=0,mid;
if (!check(x,y,1)) return 0; while (l<=r)
if (check(x,y,mid=l+r>>1)) res=mid,l=mid+1;
else r=mid-1; return res;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (pw[0]=i=1;i<=400000;++i) pw[i]=pw[i-1]*seed;
while (F.read(n))
{
for (T.clear(),F.read(m),i=1;i<=n;++i) F.gd(x),T.insert(i,x);
for (i=1;i<=m;++i)
{
F.read(opt); F.read(x); switch (opt)
{
case 1:
F.read(y); T.insert(x+1,y); break;
case 2:
T.remove(x); break;
case 3:
F.read(y); T.reverse(x,y); break;
case 4:
F.read(y); F.write(LCP(x,y)); break;
}
}
}
return F.Fend(),0;
}