[JSOI2008]火星人 题解
![[JSOI2008]火星人 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180302a.png)
题目地址：洛谷：【P4036】[JSOI2008]火星人 – 洛谷、BZOJ：Problem 1014. — [JSOI2008]火星人prefix
题目描述
火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：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函数的值。
输入输出格式
输入格式：
第一行给出初始的字符串。第二行是一个非负整数M，表示操作的个数。接下来的M行，每行描述一个操作。操作有3种，如下所示
- 询问。语法：
Q x y，x,y均为正整数。功能：计算LCQ(x,y)限制：1<=x,y<=当前字符串长度。 - 修改。语法：
R x d，x是正整数，d是字符。功能：将字符串中第x个数修改为字符d。限制：x不超过当前字符串长度。 - 插入：语法：
I x d，x是非负整数，d是字符。功能：在字符串第x个字符之后插入字符d，如果x=0，则在字符串开头插入。限制：x不超过当前字符串长度
输出格式：
对于输入文件中每一个询问操作，你都应该输出对应的答案。一个答案一行。
输入输出样例
输入样例#1：
madamimadam 7 Q 1 7 Q 4 8 Q 10 11 R 3 a Q 1 7 I 10 a Q 2 11
输出样例#1：
5 1 0 2 1
说明
1、所有字符串自始至终都只有小写字母构成。
2、M<=150,000
3、字符串长度L自始至终都满足L<=100,000
4、询问操作的个数不超过10,000个。
对于第1，2个数据，字符串长度自始至终都不超过1,000
对于第3，4，5个数据，没有插入操作。
题解
哈希与哈希值的合并
首先我们知道判断两个字符串是否相同可以使用哈希处理，而哈希也可以处理字符串的子串问题，也就是说，它能够支持区间合并。但是如果我们用维护区间的数据结构线段树，插入操作无法实现。所以我们考虑平衡树来维护这个字符串的哈希。
假如有左儿子a_1, \cdots, a_i，树根a_{i+1}，右儿子a_{i+2}, \cdots, a_n，分别写出哈希值的式子和拼起来的哈希值。
左儿子：
a_1 \times e^0 + a_2 \times e^1 + \cdots + a_i \times e^{i-1}
右儿子：
a_{i+2} \times e^0 + a_{i+3} \times e^1 + \cdots + a_n \times e^{n-i-2}
拼起来：
a_1 \times e^0 + a_2 \times e^1 + \cdots + a_i \times e^{i-1} + a_{i+1} \times e^i + a_{i+2} \times e^{i+1} + a_{i+3} \times e^{i+2} + \cdots + a_n \times e^{n-1}
观察可知，拼起来的哈希值可以通过左右儿子的哈希值通过以下计算得到
hash_{lch} + a_{mid} \times e^{llen} + hash_{rch} \times e^{llen+1}
其中llen是左儿子对应区间长度。
插入和修改
插入可以把x和x+1都splay上去，类似区间翻转（文艺平衡树：Splay原理与实现 | KSkun’s Blog）那样，只不过此时根的右儿子的左儿子为空，这个位置就是插入的位置，新建节点放进去即可。
修改可以把要修改的点splay到根，然后修改完以后update它。
二分答案
我们虽然没办法直接计算得到答案，但是我们可以二分相同部分的长度，然后再查询相同部分的哈希是否相等。
单次二分的复杂度是O(\log^2 n)的。
卡常
交到BZOJ上被卡了常，后来把两个取模删掉才过。还好进位取得小，不取模也没爆long long。
代码
// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int readint() {
register int res = 0, neg = 1;
char c = fgc();
while (c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
inline bool isop(char c) {
return c == 'Q' || c == 'R' || c == 'I';
}
inline char readop() {
char c;
while(!isop(c = fgc()));
return c;
}
inline char readchr() {
char c;
while((c = fgc()) < 'a' || c > 'z');
return c;
}
inline int readstr(char str[], int startpos) {
char c = '-';
int siz = startpos;
while(c < 'a' || c > 'z') c = fgc();
while(c >= 'a' && c <= 'z') {
str[siz++] = c;
c = fgc();
}
str[siz] = '\0';
return siz - startpos;
}
// variables
const int MAXN = 150005, MO = 1e9 + 7, E = 27;
LL ep[MAXN];
int n, m, x, y;
char str[MAXN], op, d;
inline void init() {
ep[0] = 1;
for(int i = 1; i <= 150000; i++) {
ep[i] = ep[i - 1] * E % MO;
}
}
// splay
struct Node {
LL val, chr;
int ch[2], siz, cnt, fa;
} tr[MAXN];
int tot = 0, sta[MAXN], stop = 0, rt = 0;
inline void update(int p) {
int lch = tr[p].ch[0], rch = tr[p].ch[1];
tr[p].siz = tr[lch].siz + tr[rch].siz + 1;
tr[p].val = (tr[lch].val + tr[p].chr * ep[tr[lch].siz] + tr[rch].val * ep[tr[lch].siz + 1]) % MO;
}
inline int newnode() {
int p;
if(stop > 0) {
p = sta[--stop];
} else {
p = ++tot;
}
memset(tr + p, 0, sizeof(Node));
return p;
}
inline void delnode(int a) {
sta[stop++] = a;
}
inline bool isleft(int p) {
return tr[tr[p].fa].ch[0] == p;
}
inline void rotate(int p) { // p is child
bool type = !isleft(p);
int fa = tr[p].fa, ffa = tr[fa].fa;
tr[fa].ch[type] = tr[p].ch[!type];
tr[p].ch[!type] = fa;
tr[tr[fa].ch[type]].fa = fa;
if(ffa) tr[ffa].ch[!isleft(fa)] = p;
tr[p].fa = tr[fa].fa;
tr[fa].fa = p;
update(fa);
update(p);
if(!tr[p].fa) rt = p;
}
inline void splay(int p, int tar) {
for(int fa; (fa = tr[p].fa) != tar; rotate(p)) {
if(tr[tr[p].fa].fa != tar) {
rotate(isleft(fa) == isleft(p) ? fa : p);
}
}
if(!tar) rt = p;
}
inline int find(int p, int rk) {
int lch = tr[p].ch[0], rch = tr[p].ch[1];
if(tr[lch].siz + 1 == rk) return p;
else if(tr[lch].siz >= rk) return find(lch, rk);
else return find(rch, rk - tr[lch].siz - 1);
}
inline void insert(int x, int val) {
int a = find(rt, x + 1), b = find(rt, x + 2);
splay(a, 0);
splay(b, a);
int p = newnode();
tr[b].ch[0] = p;
tr[p].fa = b;
tr[p].chr = val;
update(p);
update(b);
update(a);
}
inline LL query(int x, int len) {
int a = find(rt, x), b = find(rt, x + len + 1);
splay(a, 0);
splay(b, a);
return tr[tr[b].ch[0]].val;
}
inline int build(int fa, int l, int r) {
if(l > r) return 0;
int p = newnode();
if(!fa) rt = p;
if(l == r) {
tr[p].val = tr[p].chr = str[l] - 'a' + 1;
tr[p].fa = fa;
tr[p].siz = 1;
return p;
}
int mid = (l + r) >> 1;
tr[p].ch[0] = build(p, l, mid - 1);
tr[p].ch[1] = build(p, mid + 1, r);
tr[p].chr = str[mid] - 'a' + 1;
tr[p].fa = fa;
update(p);
return p;
}
inline int work(int x, int y) {
int l = 0, r = std::min(n - x, n - y), mid;
while(r - l > 1) {
mid = (l + r) >> 1;
if(query(x, mid) == query(y, mid)) {
l = mid;
} else {
r = mid;
}
}
return l;
}
int main() {
n = readstr(str, 2) + 2;
init();
build(0, 1, n);
m = readint();
while(m--) {
op = readop();
x = readint();
if(op == 'Q') {
y = readint();
printf("%d\n", work(x, y));
}
if(op == 'R') {
d = readchr();
int t = find(rt, x + 1);
splay(t, 0);
tr[rt].chr = d - 'a' + 1;
update(rt);
}
if(op == 'I') {
d = readchr();
insert(x, d - 'a' + 1);
n++;
}
}
return 0;
}
