我不会 runs /ll。

lzyqwq · 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]]

第一步居然没想到。考虑对 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，设当前分治区间为 [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 的个数：

但是你发现这时候出现三维偏序，肯定不能直接做。考虑拆成两部分，即用满足 \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;
}