1. 题目

传送门

2. 题解

连着做两道这种等比数列字符串哈希的题了。。。

感觉有点玄学。

哈希方法简单讲下吧，就是如果原字符串是 $str[1,len]$

那么它的哈希值就是 $\sum _ {i=1}^{len} 233^i \times str[i]$

（这里面的 $233$可以改，最好大于字符集大小。。。不知道不是质数会不会有危害，没试过）

这就是等比数列哈希，我们可以 $O(len)$预处理出 $str$的所有的前缀的哈希值，设前缀 $i$的哈希值为 $H[i]$。我们还能 $O(len)$预处理出 $233$的 $i$次幂。这样 $H[r]-2^{r-l+1}H[l-1]$就是原字符串在区间 $[l,r]$的子串的哈希值了。

这题我们只要用 splay 维护每个子树对应的区间的哈希值就行了。

然后询问 $LCQ(x,y)$就求二分答案 $ans$，求出区间 $[x,x+ans-1]$和区间 $[y,y+ans-1]$的哈希值 $H_x,H_y$，如果 $H_x=H_y$则说明最终答案是大于等于 $ans$的，否则说明答案小于 $ans$。

插入、修改都是用 splay 的提取区间操作提取一下区间，然后单点插入/修改就行了。

如果还有什么不懂的话可以看下下面的代码，可能需要注意一下 void pup(int a);（push_up) 函数。

代码：

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

typedef unsigned long long ULL;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct N {ULL d, sum; int f, s[2], sz;} e[NS];

char str[NS], opt[5];

int len, sz, root, q;

ULL data[NS], M[NS] = {1};

bool pos(int a)
{
    return e[e[a].f].s[1] == a;
}

void pup(int a)
{
    int l = e[a].s[0], r = e[a].s[1];
    e[a].sz = e[l].sz + e[r].sz + 1;
    e[a].sum = e[l].sum + M[e[l].sz] * e[a].d + M[e[l].sz + 1] * e[r].sum;
}

void rot(int a)
{
    int f = e[a].f, g = e[f].f, p = pos(a), q = pos(f);
    e[f].s[p] = e[a].s[!p], e[a].s[!p] = f, e[f].f = a;
    if (e[f].s[p]) e[e[f].s[p]].f = f;
    if (e[a].f = g) e[g].s[q] = a;
    pup(f), pup(a);
}

void splay(int a, int t)
{
    for (; e[a].f != t; rot(a))
        if (e[e[a].f].f != t)
        {
            if (pos(a) ^ pos(e[a].f)) rot(a);
            else rot(e[a].f);
        }
    if (!t) root = a;
}

int Build(int l, int r)
{
    if (l > r) return 0;
    int a = ++sz, mid = (l + r) >> 1;
    e[a].s[0] = Build(l, mid - 1), e[a].s[1] = Build(mid + 1, r);
    e[e[a].s[0]].f = e[e[a].s[1]].f = a;
    e[a].d = data[mid], pup(a); return a;
}

int find_by_order(int k)
{
    int a = root;
    while (a)
    {
        if (k < e[e[a].s[0]].sz + 1) a = e[a].s[0];
        else
        {
            k -= e[e[a].s[0]].sz + 1;
            if (!k) return a;
            a = e[a].s[1];
        }
    }
    return 0;
}

void Get_Seg(int& l, int& r)
{
    l = find_by_order(l), r = find_by_order(r + 2);
    splay(l, 0), splay(r, l);
}

ULL Query(int l, int r)
{
    Get_Seg(l, r); return e[e[r].s[0]].sum;
}

int LCQ(int x, int y)
{
    if (x > y) swap(x, y);
    int l = 0, r = (len - y + 1), mid;
    while (l < r)
    {
        mid = (l + r + 1) >> 1;
        if (Query(x, x + mid - 1) == Query(y, y + mid - 1)) l = mid;
        else r = mid - 1;
    }
    return l;
}

void Refresh(int x, char c)
{
    int l = x, r = x; Get_Seg(l, r);
    e[e[r].s[0]].d = e[e[r].s[0]].sum = c - 'a';
    pup(r), pup(l);
}

void Insert(int x, char c)
{
    int l = x + 1, r = x; Get_Seg(l, r);
    e[r].s[0] = ++sz, e[sz].f = r, e[sz].s[0] = e[sz].s[1] = 0;
    e[sz].d = e[sz].sum = c - 'a', e[sz].sz = 1;
    pup(r), pup(l);
}

int main(int argc, char const* argv[])
{
    scanf("%s", str + 1), len = strlen(str + 1);
    for (int i = 1; i <= len; i += 1) data[i + 1] = str[i] - 'a';
    for (int i = 1; i <= NS - 5; i += 1) M[i] = M[i - 1] * 233;
    root = Build(1, len + 2), IN(q);
    while (q--)
    {
        int x, y;
        scanf("%s", opt), IN(x);
        if (opt[0] == 'Q') IN(y), printf("%d\n", LCQ(x, y));
        else if (opt[0] == 'R') scanf("%s", opt), Refresh(x, opt[0]);
        else scanf("%s", opt), Insert(x, opt[0]), len++;
    }
    return 0;
}