根本就没有这样的信仰
SentencedFate · · 题解
我只是想放这个代码。
感觉复健第二天就搓出这 8K 300 行的玩意还是太牛逼了。
一个串由另外两个串拼起来，就该考虑把这个串拆成前后缀，对每个前缀和后缀分别计算出现次数。
根据上面的这个关键思想，对于一次询问
- 给定
(r, k, i) ，询问s_k 长度为i 的前缀在a_1, a_2, \dots, a_r 中的出现次数。
我们把所有被询问的串
上面的分析涉及到了
-
若
|s_k| \le B 直接按照上面说的，建 AC 自动机即可。涉及到
O(m) 次插入和O(qB) 次查询，用分块平衡复杂度得到复杂度O(qB + m \sqrt m) 。 -
若
|s_k| \ge B 设
s_k = a + b ，如果|a| \le B 或|b| \le B ，直接像1 里面一样做即可，复杂度同样是O(qB + m \sqrt m) 。否则，必然有
|a| > B 且|b| > B ，而长度> B 的串只有\dfrac{m}{B} 种，所以这种情况下本质不同的询问端点只有\dfrac{m}{B} 种，那么本质不同的询问（转成前缀之后）只有\dfrac{m^2}{B^2} 种。再对这些本质不同的询问跑与上面相同的 AC 自动机，复杂度是O\left(\dfrac{m^3}{B^2}\right) 的。
虽然
#include <queue>
#include <cstdio>
#include <algorithm>
namespace FastIn
{
const int S = 4e6 + 7;
char *p1, *p2, buf[S];
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, S, stdin), p1 == p2) ? EOF : *p1++)
inline void read(int &x)
{
x = 0;
char c = gc();
while (c < '0' || c > '9')
c = gc();
for (; c >= '0' && c <= '9'; c = gc())
x = (x << 3) + (x << 1) + (c & 15);
}
inline void readstr(char *s, int &n)
{
char c = gc(); n = 0;
while (c < 'a' || c > 'z')
c = gc();
for (; c >= 'a' && c <= 'z'; c = gc())
s[++n] = c;
}
#undef gc
}
using FastIn::read;
using FastIn::readstr;
const int MAXN = 1e5 + 7, B = 555;
int n, m, bigsid[MAXN], sppool[MAXN], revsppool[MAXN], *sp[MAXN], *revsp[MAXN], *spptr = sppool, *revspptr = revsppool;
char spool[MAXN], revspool[MAXN], *s[MAXN], *revs[MAXN], *sptr = spool, *revsptr = revspool;
struct Query { int l, r, k; } q[MAXN];
long long ans[MAXN], recans[MAXN / B + 7][MAXN / B + 7][MAXN / B + 7];
std::vector<int> hs;
std::vector<std::pair<int, int>> vq[MAXN];
std::vector<std::vector<int>> qf, qg;
std::vector<std::vector<std::vector<int>>> f, g;
#define len(i) (s[(i) + 1] - s[i])
struct DS // 用分块实现 O(sqrt) 单点加 O(1) 区间查
{
static const int B = 325;
int n, a[MAXN], t[MAXN / B + 7], L[MAXN / B + 7], R[MAXN / B + 7], bel[MAXN];
inline void init(const int &nn)
{
n = nn;
for (int l = 1, r, idx = 1; l <= n; l = r + 1, ++idx)
{
r = std::min(n, l + B - 1);
for (int i = l; i <= r; ++i)
bel[i] = idx;
L[idx] = l, R[idx] = r;
}
}
inline void clear()
{
for (int i = 1; i <= n; ++i)
a[i] = t[bel[i]] = 0;
}
inline void add(const int &x)
{
for (int i = x; i <= R[bel[x]]; ++i)
++a[i];
for (int i = bel[x] + 1; i <= bel[n]; ++i)
++t[i];
}
inline int query(const int &x) { return x ? a[x] + t[bel[x]] : 0; }
inline int query(const int &l, const int &r) { return query(r) - query(l - 1); }
};
struct ACAM // AC 自动机
{
struct ACAMNode { int ch[26], fail; } tr[MAXN];
struct Edge { int v, nxt; } e[MAXN];
int tot, tim, idx = 1, h[MAXN], dfn[MAXN], rdfn[MAXN];
DS dat;
ACAM() { tot = 1; }
inline void add(const int &u, const int &v) { e[++idx] = {v, h[u]}, h[u] = idx; }
inline void insert(const char *s, int *sp, const int &l) // sp[i] 用于记录 s 长度为 i 的前缀在 AC 自动机上对应哪个状态
{
int u = 1;
for (int i = 1; i <= l; ++i)
!tr[u].ch[s[i] - 'a'] && (tr[u].ch[s[i] - 'a'] = ++tot), sp[i] = u = tr[u].ch[s[i] - 'a'];
}
inline void getfail()
{
std::queue<int> q;
for (int i = 0; i < 26; ++i)
if (tr[1].ch[i])
tr[tr[1].ch[i]].fail = 1, q.push(tr[1].ch[i]);
else
tr[1].ch[i] = 1;
while (q.size())
{
int u = q.front(); q.pop();
for (int i = 0; i < 26; ++i)
if (tr[u].ch[i])
tr[tr[u].ch[i]].fail = tr[tr[u].fail].ch[i], q.push(tr[u].ch[i]);
else
tr[u].ch[i] = tr[tr[u].fail].ch[i];
}
}
void DFS0(const int &u)
{
dfn[u] = ++tim;
for (int i = h[u]; i; i = e[i].nxt)
DFS0(e[i].v);
rdfn[u] = tim;
}
inline void build()
{
getfail();
for (int i = 2; i <= tot; ++i)
add(tr[i].fail, i);
DFS0(1), dat.init(tot);
}
inline void clear() { dat.clear(); }
inline void update(const char *s, const int &l)
{
int u = 1;
for (int i = 1; i <= l; ++i)
dat.add(dfn[u = tr[u].ch[s[i] - 'a']]);
}
inline void query(std::vector<int> &f, const char *s, const int &l, const bool &isadd, int u = 1)
{ // 查询串 s 长度为 l 的前缀在已扫描的串中的出现次数
for (int i = 1; i <= l; ++i)
u = tr[u].ch[s[i] - 'a'],
isadd ?
f[i] += dat.query(dfn[u], rdfn[u]) :
f[i] -= dat.query(dfn[u], rdfn[u]);
}
} T[2]; // T[0] 是正串的 AC 自动机，T[1] 是反串的 AC 自动机
int main()
{
read(n), read(m), qf.assign(m + 3, std::vector<int>(B + 7)), qg.assign(m + 3, std::vector<int>(B + 7));
for (int i = 1, l; i <= n; ++i)
{
s[i] = sptr, revs[i] = revsptr, readstr(s[i], l); // s 为正串，revs 为反串
for (int j = 1; j <= l; ++j)
*++revsptr = *++sptr;
sp[i] = spptr, revsp[i] = revspptr, spptr += l, revspptr += l, // sp[k][i] 用于记录 s[k] 长度为 i 的前缀在 AC 自动机上对应哪个状态，revsp 记录的则是反串
std::reverse(revs[i] + 1, revs[i] + l + 1),
T[0].insert(s[i], sp[i], l), T[1].insert(revs[i], revsp[i], l),
l > B && (hs.push_back(i), bigsid[i] = hs.size() - 1); // hs 记录“大串”，即长度 > B 的串
}
s[n + 1] = sptr, revs[n + 1] = revsptr, sp[n + 1] = spptr, revsp[n + 1] = revspptr,
T[0].build(), T[1].build();
for (int i = 1, l, r, k; i <= m; ++i) // 首先处理所有 len(k) ≤ B 的询问
read(l), read(r), read(k), q[i] = {l, r, k},
len(k) <= B && (
vq[l - 1].emplace_back(k, -i),
vq[r].emplace_back(k, i), true
);
for (int i = 1; i <= n; ++i)
{
T[0].update(s[i], len(i)), T[1].update(revs[i], len(i));
for (const auto &[k, id] : vq[i])
if (id < 0)
T[0].query(qf[-id], s[k], len(k), false), // qf[id] 表示第 id 个询问的 f
T[1].query(qg[-id], revs[k], len(k), false); // qg[id] 表示第 id 个询问的 g
else
{
int l = len(k);
T[0].query(qf[id], s[k], l, true),
T[1].query(qg[id], revs[k], l, true);
for (int i = 1; i < l; ++i)
ans[id] += (long long)(qf[id][i]) * qg[id][l - i];
for (int i = 1; i <= l; ++i)
qf[id][i] = qg[id][i] = 0;
}
vq[i].clear();
}
T[0].clear(), T[1].clear();
for (int i = 1, l, r, k; i <= m; ++i) // 接下来处理 len(k) > B、但把 s[k] 拆成 a + b 后，|a| ≤ B 或 |b| ≤ B 的询问
l = q[i].l, r = q[i].r, k = q[i].k,
len(k) > B && (
vq[l - 1].emplace_back(k, -i),
vq[r].emplace_back(k, i), true
);
for (int i = 1; i <= n; ++i) // 处理 |a| ≤ B
{
T[0].update(s[i], len(i)), T[1].update(revs[i], len(i));
for (const auto &[k, id] : vq[i])
if (id < 0)
T[0].query(qf[-id], s[k], B, false),
T[1].query(qg[-id], revs[k] + len(k) - B - 1, B, false, len(k) - B - 1 ? revsp[k][len(k) - B - 1] : 1); // 如果要使 f[B] 对应 g[1]，则反串必须先走 len(k) - B - 1 步
else
{
int l = len(k);
T[0].query(qf[id], s[k], B, true),
T[1].query(qg[id], revs[k] + l - B - 1, B, true, l - B - 1 ? revsp[k][l - B - 1] : 1); // 注意 sp[k][0] 这个空间被串 k - 1 占用了，所以必须特判 l - B - 1 == 0
for (int i = 1; i <= B; ++i)
ans[id] += (long long)(qf[id][i]) * qg[id][B + 1 - i];
for (int i = 1; i <= B; ++i)
qf[id][i] = qg[id][i] = 0;
}
}
T[0].clear(), T[1].clear();
for (int i = 1; i <= n; ++i)
{
T[0].update(s[i], len(i)), T[1].update(revs[i], len(i));
for (const auto &[k, id] : vq[i])
if (len(k) <= (B << 1)) // 有些长度 ≤ B 的后缀的结果已经算过
{
if (len(k) == B + 1) // 如果已经算完
continue;
if (id < 0)
T[0].query(qf[-id], s[k] + B, len(k) - B - 1, false, sp[k][B]), // 长度为 B 的前缀已经被算，这意味着有 B 个后缀已经被算，还有 len - B - 1 个没有被算
T[1].query(qg[-id], revs[k], len(k) - B - 1, false);
else
{
int l = len(k);
T[0].query(qf[id], s[k] + B, l - B - 1, true, sp[k][B]),
T[1].query(qg[id], revs[k], l - B - 1, true);
for (int i = 1; i <= l - B - 1; ++i)
ans[id] += (long long)(qf[id][i]) * qg[id][l - B - i];
}
}
else // 没有长度 ≤ B 的后缀的结果已经算过
if (id < 0)
T[0].query(qf[-id], s[k] + len(k) - B - 1, B, false, sp[k][len(k) - B - 1]),
T[1].query(qg[-id], revs[k], B, false);
else
{
int l = len(k);
T[0].query(qf[id], s[k] + l - B - 1, B, true, sp[k][l - B - 1]),
T[1].query(qg[id], revs[k], B, true);
for (int i = 1; i <= B; ++i)
ans[id] += (long long)(qf[id][i]) * qg[id][B + 1 - i];
for (int i = 1; i <= B; ++i)
qf[id][i] = qg[id][i] = 0;
}
vq[i].clear();
}
qf.clear(), qf.shrink_to_fit(), // 清空空间，在上面的过程中 qf 和 qg 一共最大可占 400+ MB
qg.clear(), qg.shrink_to_fit(),
vq[0].clear(), T[0].clear(), T[1].clear(); // 前面没有用到 vq[0]，但是修改了 vq[0]，这里必须清空，为了适应 hs，下面就是 0-index 了
f.assign(hs.size(), std::vector<std::vector<int>>(hs.size(), std::vector<int>())),
g.assign(hs.size(), std::vector<std::vector<int>>(hs.size(), std::vector<int>()));
for (int i = 1, l, r, k; i <= m; ++i)
{
l = q[i].l, r = q[i].r, k = q[i].k;
if (len(k) <= ((B << 1) | 1)) // 这时，长度小于等于这个值的串答案已经算完
continue;
l = std::lower_bound(hs.begin(), hs.end(), l) - hs.begin();
r = std::upper_bound(hs.begin(), hs.end(), r) - hs.begin() - 1;
if (l > r)
continue;
if (l) // 拆成前缀后，“本质不同的询问”指的就是 (r, k) 本质不同，用“vector size 不为 0”代表“这个询问需要被计算”
f[l - 1][bigsid[k]].resize(len(k) - (B << 1) + 3),
g[l - 1][bigsid[k]].resize(len(k) - (B << 1) + 3);
f[r][bigsid[k]].resize(len(k) - (B << 1) + 3),
g[r][bigsid[k]].resize(len(k) - (B << 1) + 3);
}
for (int ii = 0, i; ii < (int)(hs.size()); ++ii)
{
i = hs[ii], T[0].update(s[i], len(i)), T[1].update(revs[i], len(i));
for (int kk = 0, k; kk < (int)(hs.size()); ++kk)
if (f[ii][kk].size())
k = hs[kk],
T[0].query(f[ii][kk], s[k] + B, len(k) - (B << 1), true, sp[k][B]),
T[1].query(g[ii][kk], revs[k] + B, len(k) - (B << 1), true, revsp[k][B]);
}
for (int i = 0; i < (int)(hs.size()); ++i)
for (int j = i; j < (int)(hs.size()); ++j)
for (int k = 0; k < (int)(hs.size()); ++k)
recans[i][j][k] = -1;
for (int ii = 1, l, r, k; ii <= m; ++ii)
{
l = q[ii].l, r = q[ii].r, k = q[ii].k;
if (len(k) <= ((B << 1) | 1))
continue;
l = std::lower_bound(hs.begin(), hs.end(), l) - hs.begin();
r = std::upper_bound(hs.begin(), hs.end(), r) - hs.begin() - 1;
if (l > r)
continue;
if (~recans[l][r][bigsid[k]]) // 本质不同的 (l, r, k) 只有 O(m³ / B³) 种，需要记忆化，如果不记忆化复杂度是错
{
ans[ii] += recans[l][r][bigsid[k]];
continue;
}
int ll = len(k);
recans[l][r][bigsid[k]] = 0;
for (int i = 1; i < ll - (B << 1); ++i)
recans[l][r][bigsid[k]] +=
(long long)(f[r][bigsid[k]][i] - (l ? f[l - 1][bigsid[k]][i] : 0))
* (g[r][bigsid[k]][ll - (B << 1) - i] - (l ? g[l - 1][bigsid[k]][ll - (B << 1) - i] : 0));
ans[ii] += recans[l][r][bigsid[k]];
}
for (int i = 1; i <= m; ++i)
printf("%lld\n", ans[i]);
return 0;
}