「雅礼集训 2017 Day1」字符串 --- 后缀自动机，乱搞

发表于

「雅礼集训 2017 Day1」字符串

%%% ???

题面

题面2

emmmm…

这个题一眼看上去是个神题，结果看了题解。。发现就是个暴力 做法十分神奇~~

问题的关键在于这个$\sum w \le 10^5$ ，在$k$很大的时候$q$很小，$q$很大的时候$k$很小，就可以设计不同的算法来搞它

随便设一个值$S$,比如$\sqrt n$

当$k \le S$时

$k$比较小，所以可以允许我们在询问串上做很多的事情

考虑一个暴力的方法!

$O(k^2)$，你没有看错，对于每个询问串，暴力统计每个区间的值，在自动机上走一走就好了

由于$m$可能比较多，所以可以用莫队，记录一下每个区间被询问了多少次，乘上对应值即可

复杂度$O(m\sqrt m +qk^2)$

当$k \ge S$时

$q$比较小，允许我们在每个询问花费更多时间

于是直接暴力。。。对于每个询问，把每个区间都做一次，只要按右端点顺序在自动机上走，同时倍增查答案即可

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 200005, ALPHA = 26;

char buf[1 << 20], *p1, *p2;
#ifndef GC
#define GC (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? 0 : *p1 ++)
#endif
inline int _R() {
	int d = 0; bool ty = 1; char t;
	while (t = GC, (t < '0' || t > '9') && t != '-') ;
	t == '-' ? (ty = 0) : (d = t - '0');
	while (t = GC, t >= '0' && t <= '9') d = (d << 3) + (d << 1) + t - '0';
	return ty ? d : -d;
}
inline void _S(char *c) {
	char *t = c, ch;
	while (ch = GC, ch == ' ' || ch == '\n' || ch == '\r') ;
	*t ++ = ch;
	while (ch = GC, ch != ' ' && ch != '\n' && ch != '\r') *t ++ = ch;
	*t = 0;
}


int n, m, q, len, L[N], R[N];

int tot, root, last, Son[N][ALPHA], Par[N], Size[N], Max[N];
void exsam(int t) {
	int np = ++ tot, q, p, nq;
	Max[np] = Max[last] + 1;
	Size[np] = 1;
	for (p = last; p && !Son[p][t]; p = Par[p])
		Son[p][t] = np;
	if (!p) Par[np] = root;
	else {
		q = Son[p][t];
		if (Max[q] == Max[p] + 1) Par[np] = q;
		else {
			nq = ++ tot;
			Par[nq] = Par[q];
			for (int i = 0; i < ALPHA; i ++) Son[nq][i] = Son[q][i];
			Max[nq] = Max[p] + 1;
			Par[np] = Par[q] = nq;
			for (; p && Son[p][t] == q; p = Par[p])
				Son[p][t] = nq;
		}
	}
	last = np;
}

int nxt_node(int &p, int len, int t) {
	if (Son[p][t]) {
		p = Son[p][t];
		return len + 1;
	}
	while (p && !Son[p][t]) p = Par[p];
	len = Max[p];
	if (Son[p][t]) {
		p = Son[p][t];
		return len + 1;
	}
	else return p = 1, len;
}

int Tote, Last[N], Next[N << 1], End[N << 1], Fa[N][20];
#ifndef ADDE
#define ADDE(ST, END) (End[++ Tote] = END, Next[Tote] = Last[ST], Last[ST] = Tote)
#endif

void dfs(int x) {
	Fa[x][0] = Par[x];
	for (int i = 1; i <= 18; i ++) Fa[x][i] = Fa[Fa[x][i - 1]][i - 1];
	for (int u, i = Last[x]; i; i = Next[i])
		u = End[i], dfs(u), Size[x] += Size[u];
}

int query(int p, int t) {
	for (int i = 18; i >= 0; i --)
		if (Max[Fa[p][i]] >= t) p = Fa[p][i];
	return Size[p];
}


char str[N];
struct Obj {
	int l, r;
} T[N];

namespace mo_s {

	struct Query {
		vector<char> str;
		int l, r, dx, id;
		bool operator < (const Query& rhs) const {
			return dx == rhs.dx ? r < rhs.r : dx < rhs.dx;
		}
	} Q[N];
	typedef long long ll;
	 ll Ans[N];

	int cnt[333][333];
	void solve() {
		int i, j, k, l, r;
		int Len = sqrt(m);
		for (i = 1; i <= q; i ++) {
			_S(str);
			for (j = 0; j < len; j ++) Q[i].str.push_back(str[j]);
			Q[i].l = _R() + 1, Q[i].r = _R() + 1;
			Q[i].id = i;
			Q[i].dx = Q[i].l / Len;
		}
		sort(Q + 1, Q + 1 + q);
		for (i = 1, l = r = 1, cnt[L[1]][R[1]] = 1; i <= q; i ++) {
			while (r < Q[i].r) r ++, cnt[L[r]][R[r]] ++;
			while (r > Q[i].r) cnt[L[r]][R[r]] --, r --;
			while (l > Q[i].l) l --, cnt[L[l]][R[l]] ++;
			while (l < Q[i].l) cnt[L[l]][R[l]] --, l ++;
			for (j = 0; j < len; j ++) {
				int p = root;
				for (k = j; k < len; k ++) {
					p = Son[p][Q[i].str[k] - 'a'];
					if (!p) break;
					Ans[Q[i].id] += 1LL * Size[p] * cnt[j][k];
				}
			}
			j = 0;
		}
		for (i = 1; i <= q; i ++) printf("%lld\n", Ans[i]);
	}

}

namespace baoli {

	typedef long long ll;
	vector<int> G[N];
	void solve() {
		int i, j, k, x, y, p, v;
		for (i = 1; i <= q; i ++) {
			_S(str);
			ll ans = 0;
			x = _R() + 1, y = _R() + 1;
			for (j = x; j <= y; j ++) G[R[j]].push_back(R[j] - L[j] + 1);

			p = root, v = 0;
			for (k = 0; k < len; k ++) {
				v = nxt_node(p, v, str[k] - 'a');
				for (vector<int> :: iterator it = G[k].begin(); it != G[k].end(); it ++) {
					if (v < *it) continue;
					ans += query(p, *it);
				}
				G[k].clear();
			}
			printf("%lld\n", ans);
		}
	}
}

int main() {
	int i, j, k;
	n = _R(), m = _R(), q = _R(), len = _R();
	_S(str + 1);
	root = tot = last = 1;
	for (i = 1; i <= n; i ++) exsam(str[i] - 'a');
	for (i = 2; i <= tot; i ++) ADDE(Par[i], i);
	dfs(1);

	for (i = 1; i <= m; i ++) L[i] = _R(), R[i] = _R();

	if (len <= sqrt(n)) mo_s :: solve();
	else baoli :: solve();
}