题意

给出n个串，m个询问形如：$S[l],S[l+1]..S[r]$在$S[t]$中出现的次数之和。 $\sum |s|\le 10^5,m\le 10^5$

思路

搞半天都搞不出一个log的

考虑上个根号算法：

所有串建ac自动机，记m为所有串的长度和。

$S[t]\ge \sqrt{m}$的询问，暴力在ac自动机上求出每个串在其中的出现次数并查询。这里是$O(m\sqrt{m})$

否则，在L-1与R处打两个询问标记。再对整个序列进行扫描，差分求解。

这里是$O(q\sqrt{m}\log m+n\log m)$

均衡一下大小可以将log放进根号里。

其实第二部分还可以再次分块去掉log

发现一题跟他反过来的547E，这个是可以用类似第二部分的方法一个log的。

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; typedef long long ll; int n, q, tot = 1, c[N][26], fail[N], m; char s[N]; #define lowbit(x) ((x) & -(x)) ll bit[N]; ll query(int x) { ll ret = 0; for (; x; x -= lowbit(x)) ret += bit[x]; return ret; } void change(int x, int v) { for(; x <= tot; x += lowbit(x)) bit[x] += v; } vector<int> tag[N], to[N], g[N]; int dfn[N], R[N], stm; void dfs(int x) { dfn[x] = ++ stm; for(int y : to[x]) dfs(y); R[x] = stm; } void build_ac() { static int Q[N]; int h = 0, t = 0; Q[t = 1] = 1; while (h < t) { int x = Q[++h]; for(int i = 0; i < 26; i++) if (c[x][i]) { Q[++t] = c[x][i]; int k = fail[x]; while(k && c[k][i] == 0) k = fail[k]; if (k) k = c[k][i]; else k = 1; fail[c[x][i]] = k; } } for(int i = 2; i <= tot; i++) to[fail[i]].push_back(i); dfs(1); } ll ans[N]; ll sum[N]; ll cnt[N]; vector<pair<int, pair<int,int>>> qry[N]; vector<pair<int, int>> ask[N]; void get_cnt(int x) { for(int y : to[x]) get_cnt(y), sum[x] += sum[y]; for(int a : tag[x]) cnt[a] += sum[x]; } int main() { freopen("f.in", "r", stdin); cin >> n >> q; int gg = 0; for(int i = 1; i <= n; i++) { scanf("%s", s + 1); m = strlen(s + 1); gg += m; int now = 1; for(int j = 1; j <= m; j++) { int r = s[j] - 'a'; if (c[now][r] == 0) c[now][r] = ++ tot; now = c[now][r]; g[i].push_back(now); } tag[now].push_back(i); } build_ac(); int fj = sqrt(gg); for(int i = 1; i <= q; i++) { int l, r, t; scanf("%d %d %d", &l, &r, &t); if (g[t].size() >= fj) qry[t].push_back(make_pair(i, make_pair(l, r))); else { ask[l - 1].push_back(make_pair(-i, t)); ask[r].push_back(make_pair(i, t)); } } for(int i = 1; i <= n; i++) if (g[i].size() >= fj) { memset(cnt, 0, sizeof cnt); memset(sum, 0, sizeof sum); for(int x : g[i]) sum[x]++; get_cnt(1); for(int i = 1; i <= n; i++) cnt[i] += cnt[i - 1]; for(pair<int,pair<int,int>> a : qry[i]) { ans[a.first] = cnt[a.second.second] - cnt[a.second.first - 1]; } } for(int i = 1; i <= n; i++) { change(dfn[g[i].back()], 1); change(R[g[i].back()] + 1, -1); for(pair<int,int> a : ask[i]) { for(int x : g[a.second]) { ans[abs(a.first)] += (a.first > 0 ? 1 : -1) * query(dfn[x]); } } } for(int i = 1; i <= q; i++) printf("%I64d\n", ans[i]); }