8.26 T4 日记和编辑器（fhq维护kmp——kmp本身含有的单射与可合并性）

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141612066

http://cplusoj.com/d/senior/p/NOD2301D

前4个操作拿fhq treap是很好维护的。

对于最后一个操作，我们可以这么思考，从kmp的匹配思路出发：

如果我们知道一个串进入的指针 jj （也就是kmp匹配到的位置），我们是可以直接预处理得到出来的 j′j' 的。

而这个东西是非常好pushup的！我们直接按照左、中、右的顺序就行了。

然后就做完了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
 #define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
 #define debag(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 1000010
int n, m, i, j, k, T, rt, Len;
char s[N], str[30], Ps[N]; 
int Q, c, u, fail[30]; 
int Gr[30][30], Fr[30][30]; 

struct FHQ_treap {
	int pri[N], w[N], a[N], cnt[N][30], f[N][30], g[N][30]; 
	int ls[N], rs[N], tot; 
	void push_up(int k) {
		int i; 
		w[k] = 1 + w[ls[k]] + w[rs[k]]; 
		for(i = 1; i <= 26; ++i) 
			cnt[k][i] = cnt[ls[k]][i] + cnt[rs[k]][i] + (a[k] == i); 
		for(i = 0; i <= Len; ++i) {
			g[k][i] = 0; f[k][i] = i; 
			if(ls[k]) g[k][i] += g[ls[k]][f[k][i]], f[k][i] = f[ls[k]][f[k][i]]; 
			g[k][i] += Gr[a[k]][f[k][i]]; f[k][i] = Fr[a[k]][f[k][i]]; 
			if(rs[k]) g[k][i] += g[rs[k]][f[k][i]], f[k][i] = f[rs[k]][f[k][i]]; 
		}
	}
	int merge(int x, int y) {
		if(!x || !y) return x + y; 
		if(pri[x] < pri[y]) {
			rs[x] = merge(rs[x], y); push_up(x); 
			return x; 
		}
		else {
			ls[y] = merge(x, ls[y]); push_up(y); 
			return y; 
		}
	}
	void split(int k, int lim, int &x, int &y) {
		if(!k) return x = y = 0, void(); 
		if(w[ls[k]] + 1 > lim) {
			y = k; split(ls[k], lim, x, ls[y]); 
		}
		else {
			x = k; split(rs[k], lim - w[ls[x]] - 1, rs[x], y); 
		}
		push_up(k); 
	}
	int new_node(int c) {
		++tot; cnt[tot][c]++; w[tot] = 1; a[tot] = c; pri[tot] = rand(); 
		for(int i = 0; i <= Len; ++i) 
			f[tot][i] = Fr[c][i], g[tot][i] = Gr[c][i]; 
		return tot; 
	}
	void print(int x) {
		if(!x) return ; 
		print(ls[x]); 
		printf("%c", (char)(a[x] + 'a' - 1)); 
		print(rs[x]); 
	}
}fhq;

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	Q = read(); scanf("%s", Ps + 1); Len = strlen(Ps + 1); 
	for(i = 1; i <= Len; ++i) Ps[i] = Ps[i] - 'a' + 1; 
	for(i = 2; i <= Len; ++i) {
		u = fail[i - 1]; 
		while(u && Ps[u + 1] != Ps[i]) u = fail[u]; 
		if(Ps[u + 1] == Ps[i]) ++u; 
		fail[i] = u; 
	}
	for(i = 1; i <= Len; ++i) debug("%d ", fail[i]); debug("\n"); 
	for(c = 1; c <= 26; ++c) 
		for(i = 0; i <= Len; ++i) {
			u = i; 
			while(u && Ps[u + 1] != c) u = fail[u]; 
			if(Ps[u + 1] == c) ++u; 
			Fr[c][i] = u; Gr[c][i] = (u == Len);
			if(Fr[c][i]) debug("(%c %d) %d %d\n", c + 'a' - 1, i, Fr[c][i], Gr[c][i]); 
		}
	while(Q--) { 
		int x, y, z, l, r; 
		scanf("%s", str); 
		if(str[0] == 'D' || str[0] == 'R') {
			l = read(); r = read(); 
			fhq.split(rt, r, y, z); fhq.split(y, l - 1, x, y); 
			rt = fhq.merge(x, z); 
		}
		if(str[0] == 'I' || str[0] == 'R') {
			if(str[0] == 'I') j = read(); 
			else j = l - 1; 
			fhq.split(rt, j, x, y); z = 0; 
			scanf("%s", s + 1); m = strlen(s + 1); 
			for(i = 1; i <= m; ++i) {
				k = fhq.new_node(s[i] - 'a' + 1); 
				z = fhq.merge(z, k); 
			}
//			fhq.print(x); debug("\n"); 
//			fhq.print(y); debug("\n"); 
//			fhq.print(z); debug("\n"); 
			rt = fhq.merge(fhq.merge(x, z), y); 
		}
		if(str[0] == 'C') {
			l = read(); r = read(); scanf("%s", s);
			fhq.split(rt, r, y, z); fhq.split(y, l - 1, x, y); 
			printf("%d\n", fhq.cnt[y][s[0] - 'a' + 1]); 
			rt = fhq.merge(fhq.merge(x, y), z); 
		}
		if(str[0] == 'S') {
			l = read(); r = read(); 
			fhq.split(rt, r, y, z); fhq.split(y, l - 1, x, y); 
			printf("%d\n", fhq.g[y][0]); 
			rt = fhq.merge(fhq.merge(x, y), z); 
		}
//		fhq.print(rt); debug("| %d\n", fhq.w[rt]); 
	}
	return 0;
}