#P2105. 增强型LCP

    ID: 1129 传统题 1000ms 256MiB 尝试: 498 已通过: 59 难度: 7 上传者: 标签>CF2200提高+/省选-FHQ Treap 分裂合并按排名分裂双哈希哈希+二分求 LCP

增强型LCP

Description

给出一个长度为 N (N≤105)N~(N\le 10^5) 的字符串 SS 和 Q (Q≤105)Q~(Q\le 10^5) 个操作,每个操作都是以下的任意一个 :

  • LCP (a, b) : 询问当前字符串 SS 中 Sa,...,nS_{a,...,n} 和 Sb,...,nS_{b,...,n} 的最长公共前缀。保证 1≤a,b,≤n1\le a,b,\le n 。
  • ADD (a, S2) : 在当前字符串 SS 的第 aa 个字符前插入字符串 S2S2 ,也就是将 SS 变成 S1,...,a−1+S2+Sa,...,nS_{1,...,a-1}+S2+S_{a,...,n} 。如果 a=n+1a=n+1 则在 SS 的最后加上 S2S2 。保证 1≤a≤n+11\le a \le n+1 。
  • CHG (a, b, S2) : 在当前字符串 SS 种将 Sa,...,bS_{a,...,b} 替换为 S2S2 。保证 b−a+1=∣S2∣, 1≤a≤b≤nb-a+1=|S2|,~1\le a\le b\le n 。
  • DEL (a, b) : 从当前字符串 SS 中删去第 aa 个字符到 第 bb 个字符,也就是将 SS 变成 S1,...,a−1+Sb+1,...,nS_{1,...,a-1}+S_{b+1,...,n} 。保证 1≤a≤b≤n1\le a\le b\le n 。

保证插入的字符串长度总和、修改的字符串长度总和均不超过 10510^5 ,ADD,CHG,DEL 的总操作数不超过 50005000 个。

Input Format

第一行是两个正整数 N,QN,Q 。

第二行是一个长度为 NN 的字符串 SS 。

接下来 QQ 行,每行描述一个操作,指令种类的输入格式为上述描述指令名称的第一个字符(L 对应 LCP,A 对应 ADD,C 对应 CHG ,D 对应 DEL)。后续的整数和字符串的输入见题目描述。

Output Format

对于每个Lcp(a,b)操作输出最长公共前缀
47
abab
L 13
A 1 ab
L 1 3
C 56 cb
L 1 3
D 1 2
L 1 3
2
4
2
0