[集训队互测 2024] 字符串

0
15011418730 LV 7 @ 2025-8-24 23:15:56
自动搬运

查看原文

来自洛谷，原作者为

lzyqwq
我永远喜欢数据结构。

搬运于2025-08-24 23:15:56，当前版本为作者最后更新于2025-05-20 21:03:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

竞选最劣做法。
给出长度为 $n$ 的字符串 $s$ ， $q$ 次询问 $i,r$ ，求： $\sum\limits_{j=1}^r[s[i,i+j-1]<s[i+j,i+2j-1]]$

$n,q\le 5\times 10^5$ ， $i+2r-1\le n$ 。
第一步居然没想到。考虑对 $s$ 后缀排序。那么对于一个合法的 $s[i+j,i+2j-1]$ ，一定有 $s[i,n]<s[i+j,n]$ 。那么考虑枚举 $s[i+j,n]$ 这个后缀，求：
$$\sum\limits_{k=\text{rk}_i+1}^n[\text{sa}_k\in [i+1,i+r]\land s[i,\text{sa}_k-1]<s[\text{sa}_k,2\text{sa}_k-i-1]] $$
由于已经满足 $k>\text{rk}_i$ ，那么如果 $|\text{LCP}(s[i,n],s[\text{sa}_k,n])|<\text{sa}_k-i$，那么两个后缀第一个失配位置在 $s[i,\text{sa}_k-1]$ 和 $s[\text{sa}_k,2\text{sa}_k-i-1]$ 内，而且这个失配位置就是两个串的第一个失配位置。根据后缀的大小关系可以得出失配位置的大小关系是前者小于后者，从而得到 $s[i,\text{sa}_k-1]<s[\text{sa}_k,2\text{sa}_k-i-1]$ 。同理，若 $|\text{LCP}(s[i,n],s[\text{sa}_k,n])|\ge \text{sa}_k-i$，会导致两个后缀的最长公共前缀覆盖这两个串，从而导致两个串相等。

因此可以改写第二个条件，即求：
$$\sum\limits_{k=\text{rk}_i+1}^n[\text{sa}_k\in [i+1,i+r]\land |\text{LCP}(s[i,n],s[\text{sa}_k,n])|<\text{sa}_k-i] $$
接下来进入纯 ds 部分，也是经典老番之《两只老哥跑得快，序列分治真可爱.jpg》。

考虑用 $\text{height}$ 数组（下简称为 $h$ ）转化 $|\text{LCP}|$ 的限制，令 $I=\text{rk}_i$ ，把询问挂在 $I$ 上，那么我们要求满足如下限制的 $k$ 个数：
- $k>I$ 。
- $\text{sa}_k\in [\text{sa}_I+1,\text{sa}_I+r]$ 。
- $\min\limits_{t=I+1}^kh_t<\text{sa}_k-\text{sa}_I$ 。
看上去像个三维偏序。于是用分治处理 $k>I$ ，设当前分治区间为 $[L,R]$ ，中点 $m=\left\lfloor\dfrac{L+R}{2}\right\rfloor$ 。考虑右半边对左半边的贡献。

从 $m$ 到 $L$ 扫描 $I$ ，维护 $\text{mn}=\min\limits_{t=I+1}^mh_t$ 。对于右半区间，维护 $f_k=\min\limits_{t=m+1}^kh_t$ ，那么第三个限制被转化为：
$\min\{\text{mn},f_k\}<\text{sa}_k-\text{sa}_I$
由于 $f_k$ 不升，一定存在分界点 $p$ ，使得 $k\in [m+1,p-1]$ 时 $\text{mn}\le f_k$ ； $k\in [p,R]$ 时 $\text{mn}> f_k$ 。考虑分别计算两类贡献。

第一类贡献中第三个限制为 $\text{mn}<\text{sa}_k-\text{sa}_I$ ，那么变成求满足以下条件的 $k$ 个数：
- $k\in [m+1,p-1]$ 。
- $\text{sa}_k\in [\text{sa}_I+\text{mn}+1,\text{sa}_I+r]$。
容易二维数点解决。考虑类似地拆第二类贡献，即要求满足以下条件的 $k$ 的个数：
- $k\in [p,R]$ 。
- $\text{sa}_k\in[\text{sa}_I+1,\text{sa}_I+R]$ 。
- $f_k<\text{sa}_k-\text{sa}_I$ 。
但是你发现这时候出现三维偏序，肯定不能直接做。考虑拆成两部分，即用满足 $\begin{cases}\text{mn}<\text{sa}_k-\text{sa}_I\\k\in [p,R]\\\text{sa}_k\in [\text{sa}_I+1,\text{sa}_I+R]\end{cases}$ 的 $k$ 的个数加上 $\begin{cases}f_k<\text{sa}_k-\text{sa}_I\le \text{mn}\\k\in [p,R]\\\text{sa}_k\in [\text{sa}_I+1,\text{sa}_I+R]\end{cases}$ 的 $k$ 的个数。

前者可以与第一类贡献合并变成 $[m+1,R]$ 内 $\text{sa}_k\in [\text{sa}_I+\text{mn}+1,\text{sa}_I+r]$ 的 $k$ 个数，容易用一个全局 BIT 维护。至于后者，我们发现第一条限制已经满足 $f_k<\text{mn}$ 即 $k\in [p,R]$ ，所以直接忽略第二个限制。那么问题变成关于 $\text{sa}_k-f_k$ 和 $\text{sa}_k$ 的二维数点。扫描线 + BIT 维护即可。

认为 $n,q$ 同阶，时间复杂度 $\mathcal{O}\left(n\log^2 n\right)$ ，空间复杂度 $\mathcal{O}(n)$ 。~~优点是空间线性。~~

类似套路题目：

代码很好写：
```
#include <bits/stdc++.h>
using namespace std; const int N = 500005; char s[N];
int c, n, q, a[N], f[N]; vector<pair<int, int>> g[N];
struct QR { int l, r, i; } d[N]; pair<int, int> e[N];
struct SA {
	int sa[N], rk[N], h[N], c[N], y[N];
	void B() {
		for (int i = 1; i <= n; ++i) ++c[s[i]];
		for (int i = 1; i < N; ++i) c[i] += c[i - 1];
		for (int i = 1; i <= n; ++i) sa[c[s[i]]--] = i;
		for (int i = 2, t = rk[sa[1]] = 1; i <= n; ++i)
			rk[sa[i]] = (s[sa[i]] == s[sa[i - 1]] ? t : ++t);
		for (int w = 1, t; w <= n; w <<= 1) {
			t = 0; for (int i = n - w + 1; i <= n; ++i) y[++t] = i;
			for (int i = 1; i <= n; ++i) if (sa[i] > w) y[++t] = sa[i] - w;
			memset(c, 0, sizeof c); for (int i = 1; i <= n; ++i) ++c[rk[i]];
			for (int i = 1; i <= n; ++i) c[i] += c[i - 1];
			for (int i = n; i >= 1; --i) sa[c[rk[y[i]]]--] = y[i];
			swap(rk, y); t = rk[sa[1]] = 1;
			for (int i = 2; i <= n; ++i)
				rk[sa[i]] = (y[sa[i]] == y[sa[i - 1]] &&
				             y[sa[i] + w] == y[sa[i - 1] + w] ? t : ++t);
			if (t == n) break;
		}
		for (int i = 1, k = 0; i <= n; ++i) {
			if (i == sa[1]) { k = 0; continue; } if (k) --k;
			while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k; h[rk[i]] = k;
		}
	}
} S;
struct BIT1 {
	int a[N]; void U(int x, int y) { for (; x <= n; x += x & -x) a[x] += y; }
	int Q(int x) { int r = 0; for (; x; x -= x & -x) r += a[x]; return r; }
	int Q(int l, int r) { return l > r ? 0 : Q(r) - Q(l - 1); }
} t;
void F(int l, int r) {
	if (l == r) return; int m = l + r >> 1, c = 0, b = 0; f[m] = N;
	for (int i = m + 1; i <= r; ++i)
		f[i] = min(f[i - 1], S.h[i]), t.U(S.sa[i], 1),
		e[++b] = {S.sa[i] - f[i], S.sa[i]};
	for (int i = m, mn = N; i >= l; --i) {
		for (auto [j, x] : g[S.sa[i]])
			a[j] += t.Q(S.sa[i] + mn + 1, S.sa[i] + x),
			d[++c] = {S.sa[i] + 1, S.sa[i] + min(x, mn), j};
		mn = min(mn, S.h[i]);
	}
	for (int i = m + 1; i <= r; ++i) t.U(S.sa[i], -1);
	stable_sort(d + 1, d + c + 1, [&](QR u, QR v) { return u.l > v.l; });
	stable_sort(e + 1, e + b + 1, greater<pair<int, int>>());
	for (int i = 1, j = 1; i <= c; ++i) {
		for (; j <= b && e[j].first >= d[i].l; ++j) t.U(e[j].second, 1);
		a[d[i].i] += t.Q(d[i].l, d[i].r);
		if (i == c) for (--j; j; --j) t.U(e[j].second, -1);
	}
	F(l, m); F(m + 1, r);
}
int main() {
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin >> c >> n >> q;
	for (int i = 1; i <= n; ++i) cin >> s[i]; S.B();
	for (int i = 1, j, r; i <= q; ++i) cin >> j >> r, g[j].emplace_back(i, r);
	F(1, n); for (int i = 1; i <= q; ++i) cout << a[i] << '\n'; return 0;
}
```