Description

火星人最近研究了一种操作: 求一个字串两个后缀的公共前缀. 比方说, 有这样一个字符串:madamimadam, 我们将这个字符串的各个字符予以标号:

序号：1 2 3 4 5 6 7 8 9 10 11

字符：m a d a m i m a d a m

现在, 火星人定义了一个函数 \(LCQ(x, y)\), 表示: 该字符串中第 \(x\) 个字符开始的字串, 与该字符串中第 \(y\) 个字符开始的字串, 两个字串的公共前缀的长度. 比方说,\(LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0\). 在研究 LCQ 函数的过程中, 火星人发现了这样的一个关联: 如果把该字符串的所有后缀排好序, 就可以很快地求出 \(LCQ\) 函数的值; 同样, 如果求出了 LCQ 函数的值, 也可以很快地将该字符串的后缀排好序. 尽管火星人聪明地 找到了求取 \(LCQ\) 函数的快速算法, 但不甘心认输的地球人又给火星人出了个难题: 在求 取 \(LCQ\) 函数的同时, 还可以改变字符串本身. 具体地说, 可以更改字符串中某一个字符的 值, 也可以在字符串中的某一个位置插入一个字符. 地球人想考验一下, 在如此复杂的问题 中, 火星人是否还能够做到很快地求取 \(LCQ\) 函数的值.

Input

第一行给出初始的字符串. 第二行是一个非负整数 \(m\), 表示操作的个数. 接下来的 \(m\) 行, 每行描述一个操作. 操作有 \(3\) 种, 如下所示:

  1. 询问. 语法:Q x y,\(x, y\) 均为正整数. 功能: 计算 \(LCQ(x, y)\); 限制:\(1 \leq x, y \leq 当前字符串长度\).
  2. 修改. 语法:R x d,\(x\) 是正整数,\(d\) 是字符. 功能: 将字符串中第 \(x\) 个数 修改为字符 \(d\). 限制:\(x\) 不超过当前字符串长度.
  3. 插入: 语法:I x d,\(x\) 是非负整数,\(d\) 是字符. 功能: 在字符串第 \(x\) 个字符之后插入字符 \(d\), 如果 \(x = 0\), 则在字符串开头插入. 限制:\(x\) 不超过当前字符串长度.

Output

对于输入文件中每一个询问操作, 你都应该输出对应的答案. 一个答案一行.

Sample Input

madamimadam
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11

Sample Output

5
1
0
2
1

Data Range

所有字符串自始至终都只有小写字母构成.

对于所有数据, 总满足:\(m \leq 150000\)

字符串长度 \(L\) 自始至终都满足:\(L \leq 100000\)

询问操作的个数不超过 \(10000\) 个.

Explanation

在 Splay 上搞高级插入与修改, 然后再搞一个 Hash 函数出来, 来判断两个字符串是否 相等. 最开始我用了一个移位函数, 结果果断被卡 (233), 后来还是参照了黄学长的代码用了乘法加模质数的方法, 结果不停 TLE

开始以为是像之前那样的卡 long long (雾), 但是改成 int 以后就会不停地 WA, 结果 在本机上用 pyjudge 测了几发以后发现 int 溢出了

把这堆改完以后就又变回了 TLE. 然后看看本蒟蒻的程序差不多要比黄学长的程序要慢上 60% 左右, 这才意识到是自己的问题. 随即查看了一些不太好的地方, 比如应该二分插入 字符串 (这个可以使初始情况就是最优的), 虽然优化以后并没有性能上的显著提升, 而且 交上去还是会 TLE. 搞完以后突然意识到一件事情:

我的所有 Hash 值都在 int 以内, 对吧? 我的所有 Hash 都是用 long long 存的, 对吧? 那我为什么还要在乘他们的时候用上模运算呢 (我脑残了)? 所以去掉 Hash 函数里的四个 模操作中的三个, 当然结果还是对的!

就这样魔改了一发交上去就 AC 了~ 我好弱, Splay 写的常数这么大......

Source Code


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define range(_begin,_end) rep(_,_begin,_end)
using namespace std;
typedef long long lli;
const int maxn = 200100;
const lli modr = 9875321;

// lli bin_right_rotate(lli dig, lli cnt)
// {
//     lli digs = 24;
//     cnt %= digs;
//     lli siz = (1ll << digs) - 1,
//         cntsiz = (1ll << cnt) - 1;
//     dig = dig & siz;
//     return (dig >> cnt) | ((dig & cntsiz) << (digs - cnt));
// }
//
// lli concat_hash(lli hash_a, int len_a, lli hash_b, int len_b)
// {
//     return bin_right_rotate(hash_a, 3 * len_b) ^ hash_b;
// }

lli pwr[maxn];
inline void preproc_hash_pwr(void)
{
    pwr[0] = 1;
    for (int i = 1; i <= 150010; i++)
        pwr[i] = pwr[i - 1] * 27 % modr;
    return ;
}

inline lli concat_hash(lli hash_a, int len_a, lli hash_b, int len_b, lli hash_c, int len_c)
{
    lli hsh = (hash_a +
        hash_b * pwr[len_a] +
        hash_c * pwr[len_a + len_b]) % modr;
    return hsh;
}

class SplayTree
{
public:
    int ch[maxn][2], par[maxn];
    int val[maxn], size[maxn];
    lli vhash[maxn];
    int root, ncnt, n;
    #define lc(__x) ch[__x][0]
    #define rc(__x) ch[__x][1]
    inline int make_node(int v, int p)
    {
        lc(p) = rc(p) = par[p] = 0;
        vhash[p] = val[p] = v;
        size[p] = 1;
        return p;
    }
    inline int make_node(int v)
    {
        int p = ++ncnt;
        return make_node(v, p);
    }
    inline void update_data(int p)
    {
        size[p] = size[lc(p)] + size[rc(p)] + 1;
        // printf("update data %d %d %d :: %lld\n", p, lc(p), rc(p), vhash[p]);
        vhash[p] = concat_hash(
            vhash[lc(p)], size[lc(p)],
            val[p], 1,
            vhash[rc(p)], size[rc(p)]);
        // printf("update data %d -> %lld\n", p, vhash[p]);
        return ;
    }
    inline void rotate(int p)
    {
        int q = par[p], g = par[q];
        int x = p == rc(q), y = q == rc(g);
        ch[q][x] = ch[p][!x]; if (ch[q][x]) par[ch[q][x]] = q;
        ch[p][!x] = q; par[q] = p;
        if (g) ch[g][y] = p; par[p] = g;
        update_data(q);
        update_data(p);
        // if (g) update_data(g);
        return ;
    }
    inline void splay(int p, int t)
    {
        for (int q = 0; (q = par[p]) && q != t; rotate(p))
            if (par[q] && par[q] != t)
                rotate((p == rc(q)) == (q == rc(par[q])) ? q : p);
        if (t == 0) root = p;
        return ;
    }
    inline int find(int sz)
    {
        int p = root;
        while (p) {
            if (sz <= size[lc(p)]) {
                p = lc(p); continue; }
            sz -= size[lc(p)];
            if (sz == 1) return p;
            sz--; p = rc(p);
        }
        return p;
    }
    inline void insert(int l, int v)
    {
        n++; // Addition to the tree
        int p = find(l + 1), q = find(l + 2);
        splay(p, 0);
        splay(q, root);
        int r = make_node(v);
        par[r] = q; lc(q) = r;
        size[q]++, size[p]++;
        update_data(r);
        update_data(q);
        update_data(p);
        return ;
    }
    inline void modify(int pos, int v)
    {
        int p = find(pos + 1);
        splay(p, 0);
        val[p] = v;
        update_data(p);
        return ;
    }
    lli get_hash(int l, int r)
    {
        int lp = find(l + 1 - 1),
            rp = find(r + 1 + 1);
        splay(lp, 0);
        splay(rp, root);
        // printf("get hash %d, %d -> %d, %d : %d\n", l, r, lp, rp,
        //     size[lc(rp)]);
        lli hsh = vhash[lc(rp)];
        return hsh;
    }
    int query_lcq(int pos_a, int pos_b)
    {
        int l = 1, r = min(n - pos_a + 1, n - pos_b + 1), res = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            lli hash_a = get_hash(pos_a, pos_a + mid - 1),
                hash_b = get_hash(pos_b, pos_b + mid - 1);
            // printf("lcq %d -> %d : %lli ==== %d -> %d : %lli\n",
            //     pos_a, pos_a+mid-1, hash_a, pos_b, pos_b+mid-1, hash_b);
            if (hash_a == hash_b)
                res = mid, l = mid + 1;
            else
                r = mid - 1;
        }
        return res;
    }
    int build(int l, int r, char arr[])
    {
        if (l > r) return 0;
        int mid = (l + r) / 2;
        int p = make_node(arr[mid], mid + 2);
        lc(p) = build(l, mid - 1, arr);
        if (lc(p)) par[lc(p)] = p;
        rc(p) = build(mid + 1, r, arr);
        if (rc(p)) par[rc(p)] = p;
        update_data(p);
        return p;
    }
    void init(int n_, char arr[])
    {
        n = n_;
        ncnt = n + 2;
        root = make_node(0, 1);
        rc(root) = make_node(0, 2);
        par[rc(root)] = root;
        size[root] = n + 2;
        size[rc(root)] = n + 1;
        lc(rc(root)) = build(1, n, arr);
        par[lc(rc(root))] = rc(root);
        splay(3, 0);
        return ;
    }
} st;

int n, m;
char str[maxn];
char qstr[32], istr[32];

int main(int argc, char** argv)
{
    scanf("%s%d", str + 1, &m);
    n = strlen(str + 1);
    preproc_hash_pwr();
    for (int i = 1; i <= n; i++)
        str[i] = str[i] - 'a' + 1;
    st.init(n, str);
    for (int idx = 1; idx <= m; idx++) {
        int l, r;
        scanf("%s", qstr);
        if (qstr[0] == 'Q') {
            scanf("%d%d", &l, &r);
            int lcq = st.query_lcq(l, r);
            printf("%d\n", lcq);
        } else if (qstr[0] == 'R') {
            scanf("%d%s", &l, istr);
            st.modify(l, istr[0] - 'a' + 1);
        } else if (qstr[0] == 'I') {
            scanf("%d%s", &l, istr);
            st.insert(l, istr[0] - 'a' + 1);
        } else if (qstr[0] == 'A') {
            scanf("%d%d", &l, &r);
            lli hsh = st.get_hash(l, r);
            printf("%llx\n", hsh);
        }
    }
    return 0;
}