【题意】给出一个长度为n的01串，有m个操作。操作有以下几种：

              1 p c在第p个字符后插入c

              2 p    删除第p个字符

              3 p1 p2 翻转p1到p2的字符串

              4 p1 p2 求从p1开始和p2开始的两个后缀的LCP

【解题方法】

             参见白书。利用字符串hash，可以维护一个区间的字符串的hash值，利用伸展树可以轻松的完成前3种操作，对于操作4，二分一下长度，将取出的两个串的hash值进行比较，就能判断是否相同。

【PS】这题有点恶心，在LCP提取区间的时候，把Rotateto写成了Rotate，查了半天错才知道。

【代码君】

//
//Created by just_sort 2016/10/15
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int pp = 239641;
const int maxn = 555555;
uLL p[maxn],Hash[maxn][2];
char s[maxn];
int ch[maxn][2],pre[maxn],val[maxn],sz[maxn],rev[maxn],root,tot;

void Treaval(int x) {
    if(x) {
        Treaval(ch[x][0]);
        printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,val = %2d\n",x,ch[x][0],ch[x][1],pre[x],sz[x],val[x]);
        Treaval(ch[x][1]);
    }
}
void debug() {printf("%d\n",root);Treaval(root);}

void Newnode(int &rt,int fa,int k)
{
    rt = ++tot;
    ch[rt][0] = ch[rt][1] = rev[rt] = 0;
    sz[rt] = 1;
    pre[rt] = fa;
    Hash[rt][0] = Hash[rt][1] = val[rt] = k;
}
void pushup(int rt)
{
    sz[rt] = sz[ch[rt][0]] + sz[ch[rt][1]] + 1;
    int len = sz[ch[rt][0]];
    Hash[rt][0] = Hash[ch[rt][0]][0] + val[rt]*p[len] + Hash[ch[rt][1]][0]*p[len+1];
    len = sz[ch[rt][1]];
    Hash[rt][1] = Hash[ch[rt][1]][1] + val[rt]*p[len] + Hash[ch[rt][0]][1]*p[len+1];
}
void f(int rt)
{
    if(!rt) return ;
    swap(ch[rt][0], ch[rt][1]);
    swap(Hash[rt][0], Hash[rt][1]);
    rev[rt] ^= 1;
}
void pushdown(int rt)
{
    if(rev[rt]){
        f(ch[rt][0]);
        f(ch[rt][1]);
        rev[rt] = 0;
    }
}
void Rotate(int x,int kind)
{
    int y = pre[x];
    pushdown(y); pushdown(x);
    ch[y][kind^1] = ch[x][kind];
    pre[ch[x][kind]] = y;
    if(pre[y]) ch[pre[y]][ch[pre[y]][1] == y] = x;
    pre[x] = pre[y];
    ch[x][kind] = y;
    pre[y] = x;
    pushup(y);
}
void Splay(int r,int goal)
{
    pushdown(r);
    while(pre[r]!=goal)
    {
        if(pre[pre[r]]==goal)
        {
            Rotate(r,ch[pre[r]][0]==r);
            pushdown(pre[r]);
            pushdown(r);
        }
        else
        {
            pushdown(pre[pre[r]]);
            pushdown(pre[r]);
            pushdown(r);
            int y=pre[r];
            int kind=(ch[pre[y]][0]==y);
            if(ch[y][kind]==r)
            {
                Rotate(r,!kind);
                Rotate(r,kind);
            }
            else
            {
                Rotate(y,kind);
                Rotate(r,kind);
            }
        }
    }
    pushup(r);
    if(goal==0) root=r;
}
void RotateTo(int k, int goal)
{
    int rt = root;
    pushdown(rt);
    while(sz[ch[rt][0]] != k)
    {
        if(sz[ch[rt][0]] > k)
            rt = ch[rt][0];
        else{
            k -= (sz[ch[rt][0]] + 1);
            rt = ch[rt][1];
        }
        pushdown(rt);
    }
    Splay(rt,goal);
}
void Insert(int k, int c)
{
    RotateTo(k, 0);
    RotateTo(k+1, root);
    int rt = ch[root][1];
    Newnode(ch[rt][0], rt, c);
    pushup(rt);
    pushup(root);
}
void Delete(int p)
{
    RotateTo(p-1, 0);
    RotateTo(p+1, root);
    int rt  =ch[root][1];
    ch[rt][0] = 0;
    pushup(rt);
    pushup(root);
}

void Reverse(int L, int R)
{
    RotateTo(L-1, 0);
    RotateTo(R+1, root);
    f(ch[ch[root][1]][0]);
    pushup(ch[root][1]);
    pushup(root);
}

bool judge(int x,int y,int len)
{
    uLL xval, yval;
    RotateTo(x-1, 0);
    if(sz[ch[root][1]] - 1 < len) return 0;
    RotateTo(x+len, root);
    int rt = ch[ch[root][1]][0];
    xval = Hash[rt][rev[rt]];
    RotateTo(y-1, 0);
    if(sz[ch[root][1]] - 1 < len) return 0;
    RotateTo(y+len, root);
    rt = ch[ch[root][1]][0];
    yval = Hash[rt][rev[rt]];
    return xval == yval;
}
int Lcp(int x,int y)
{
    int L = 1, R = sz[root] - 1;
    if(!judge(x, y, 1)) return 0;
    while(R - L > 1)
    {
        int mid = (L + R)>>1;
        if(judge(x, y, mid)) L = mid;
        else R = mid;
    }
    return L;
}
void Build(int l, int r,int &rt, int fa)
{
    if(l > r) return;
    int m = (l + r)>>1;
    Newnode(rt, fa, s[m] - '0');
    Build(l, m-1, ch[rt][0], rt);
    Build(m+1, r, ch[rt][1], rt);
    pushup(rt);
}
void Init(int n)
{
    ch[0][0] = ch[0][1] = sz[0] = 0;
    Hash[0][0] = Hash[0][1] = 0;
    rev[0] = pre[0] = val[0] = 0;
    root = tot = 0;
    Newnode(root, 0, 0);
    Newnode(ch[root][1], root, 0);
    Build(0, n-1, ch[ch[root][1]][0], ch[root][1]);
    pushup(ch[root][1]);
    pushup(root);
}

int main()
{
    p[0] = 1;
    for(int i = 1; i < maxn; i++) p[i] = p[i-1] * pp;
    int n, m;
    while(scanf("%d%d",&n,&m) != EOF)
    {
        scanf("%s", s);
        Init(n);
        //debug();
        int op, p1, p2, c;
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d", &op, &p1);
            if(op == 1)
            {
                scanf("%d", &c);
                Insert(p1, c);
                //debug();
            }
            else if(op == 2){
                Delete(p1);
                //debug();
            }
            else if(op == 3){
                scanf("%d", &p2);
                Reverse(p1,p2);
                //debug();
            }
            else{
                scanf("%d", &p2);
                int ans = Lcp(p1, p2);
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}