【luogu P4036】【ybt金牌导航4-5-3】火星人

火星人

题目链接：luogu P4036 / ybt金牌导航4-5-3

题目大意

给你一个字符串，要你维护三个东西。

修改字符串的一个字符，往字符串的一个地方插入一个字符，询问两个后缀的最长公共前缀。

思路

如果没有修改和插入，我们容易想到 SA。

但是它问题是它会修改。

那我们想到 SA 就搞不了，我们考虑垃圾一点的算法，二分+哈希。

哈希的话你就需要维护快速求一段区间的哈希值。

那区间求值，还有插入，自然想到平衡树。

由于它这个看起来比较玄学？我们用替罪羊。（不过好像用 Treap Splay 什么的也可以）

然后关于哈希的计算大概就是 h s n o w = h s l s n o w × d i s z r s n o w + 1 + v a l n o w × d i s z r s n o w + h s r s n o w hs_{now}=hs_{ls_{now}}\times di^{sz_{rs_{now}}+1}+val_{now}\times di^{sz_{rs_{now}}}+hs_{rs_{now}} hsnow​=hslsnow​​×diszrsnow​​+1+valnow​×diszrsnow​​+hsrsnow​​

d i x di^x dix 我们预处理，就是哈希的底数。

然后别的正常搞搞就是了。

（记得 up）

代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#define dii 131
#define alph (0.75)
#define logalph (log(4.0) - log(3.0))
#define ull unsigned long long

using namespace std;

ull di[150001];
int m, n, a[300001], x, y, maxdeg, tmp;
char c[300001], op;

int sta[3000001], root;
int ls[3000001], rs[3000001], sz[3000001];
ull hs[3000001], val[3000001];

int newpoint() {
	int re = sta[sta[0]--];
	ls[re] = rs[re] = 0;
	sz[re] = 0;
	val[re] = 0;
	return re;
}

void up(int now) {
	sz[now] = sz[ls[now]] + sz[rs[now]] + 1;
	hs[now] = hs[ls[now]] * di[sz[rs[now]] + 1] + val[now] * di[sz[rs[now]]] + hs[rs[now]];
}

int build(int l, int r) {
	if (l > r) return 0;
	
	int now = newpoint();
	
	val[now] = a[(l + r) >> 1];
	sz[now] = 1;
	
	if (l != r) {
		int mid = (l + r) >> 1;
		ls[now] = build(l, mid - 1);
		rs[now] = build(mid + 1, r);
	}
	
	up(now);
	
	return now;
}

ull Query(int now, int l, int r, int L, int R) {
	if (L == l && r == R) {
		return hs[now];
	}
	
	int mid = sz[ls[now]];//都在左边或都在右边
	if (R < l + mid) return Query(ls[now], l, l + mid - 1, L, R);
	if (L > l + mid) return Query(rs[now], l + mid + 1, r, L, R);
	
	ull re = 0;//分成三部分，左边的，这个位置的，右边的
	if (L < l + mid) re = Query(ls[now], l, l + mid - 1, L, l + mid - 1);
	if (L <= l + mid && l + mid <= R) re = re * di[1] + val[now];
	if (l + mid < R) re = re * di[R - (l + mid)] + Query(rs[now], l + mid + 1, r, l + mid + 1, R);
	return re;
}

void make_bian(int now) {//拍扁
	if (ls[now]) make_bian(ls[now]);
	sta[++sta[0]] = now;
	a[++tmp] = val[now];
	if (rs[now]) make_bian(rs[now]);
}

void change_(int now, int l, int r, int pl, int num) {
	int mid = sz[ls[now]];
	if (pl <= l + mid - 1) change_(ls[now], l, l + mid - 1, pl, num);
		else if (pl == l + mid) val[now] = num;
			else change_(rs[now], l + mid + 1, r, pl, num);
	up(now);
}

bool insert_(int &now, int pl, int num, int deg) {
	if (!now) {
		now = newpoint();
		sz[now] = 1;
		val[now] = hs[now] = num;
		return deg <= maxdeg;
	}
	
	bool ck;
	int mid = sz[ls[now]];
	if (pl <= sz[ls[now]]) ck = insert_(ls[now], pl, num, deg + 1);
		else ck = insert_(rs[now], pl - sz[ls[now]] - 1, num, deg + 1);
	
	up(now);
	if (ck && (alph * sz[now] + 6 < sz[ls[now]] || alph * sz[now] + 6 < sz[rs[now]])) {
		tmp = 0;
		make_bian(now);
		now = build(1, sz[now]);
		
		return 0;
	}
	
	return ck;
}

int main() {
	di[0] = 1;
	for (int i = 1; i <= 150000; i++)
		di[i] = di[i - 1] * dii;
	
	for (int i = 1; i < 3000000; i++)
		sta[++sta[0]] = 3000000 - i;
	
	scanf("%s", c + 1);
	n = strlen(c + 1);
	for (int i = 1; i <= n; i++) {
		a[i] = c[i] - 'a' + 1;
	}
	root = build(1, n);
	
	scanf("%d", &m);
	
	while (m--) {
		op = getchar();
		while (op != 'Q' && op != 'R' && op != 'I') op = getchar();
		
		if (op == 'Q') {
			scanf("%d %d", &x, &y);
			
			int l = 0, r = min(n - x + 1, n - y + 1), ans = 0;
			while (l <= r) {//二分
				int mid = (l + r) >> 1;
				if (Query(root, 1, n, x, x + mid - 1) == Query(root, 1, n, y, y + mid - 1)) {
					ans = mid;
					l = mid + 1;
				}
				else r = mid - 1;
			}
			
			printf("%d\n", ans);
			
			continue;
		}
		if (op == 'R') {
			scanf("%d", &x);
			c[1] = getchar();
			while (c[1] < 'a' || c[1] > 'z') c[1] = getchar();
			y = c[1] - 'a' + 1;
			
			change_(root, 1, n, x, y);
			
			continue;
		}
		if (op == 'I') {
			scanf("%d", &x);
			c[1] = getchar();
			while (c[1] < 'a' || c[1] > 'z') c[1] = getchar();
			y = c[1] - 'a' + 1;
			
			n++;
			maxdeg = log(1.0 * n) / logalph;
			insert_(root, x, y, 0);
			
			continue;
		}
	}
	
	return 0;
}