洛谷P4094 [HEOI2016/TJOI2016] 字符串题解

题目链接：P4094 [HEOI2016/TJOI2016] 字符串

题意：

cxy 过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为 \(n\) 的字符串 \(s\)，和 \(m\) 个问题。cxy 必须正确回答这 \(m\) 个问题，才能打开箱子拿到礼物，升职加薪，出任 CEO，嫁给高富帅，走上人生巅峰。

每个问题均有 \(a,b,c,d\) 四个参数，问你子串 \(s[a..b]\) 的所有子串和 \(s[c..d]\) 的最长公共前缀的长度的最大值是多少？cxy 并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？

输入格式：

输入的第一行有两个正整数 \(n,m\)，分别表示字符串的长度和询问的个数。

接下来一行是一个长为 \(n\) 的字符串。接下来 \(m\) 行，每行有 \(4\) 个数 \(a,b,c,d\)，表示询问 \(s[a..b]\) 的所有子串和 \(s[c..d]\) 的最长公共前缀的最大值。

输出格式：

对于每一次询问，输出答案。

数据范围：

\(1\le n,m\le 100,000\)，字符串中仅有小写英文字母，\(a\le b\)，\(c\le d\)，\(1\le a,b,c,d\le n\)。

前置知识：后缀数组及其 height 数组的性质。

下文中 \(\mathrm{lcp}(\operatorname{suf} i,\,\operatorname{suf} j)\) 定义为后缀 \(i,j\) 的最长公共前缀，\(\mathrm{LCP}(i,j)\) 定义为排名 \(i,j\) 的后缀的最长公共前缀。

考虑二分这个最大值 \(\rm len\) ，那么问题就变成了

判断是否存在后缀 \(\operatorname{suf} i\) 满足 \(i \in [a, b - \mathrm{len} + 1]\) 且 \(\operatorname{lcp}(\operatorname{suf} i, \operatorname{suf} c) \ge \mathrm{len}\) 。

不考虑 \(i\) 的取值范围的话很简单，考虑构建后缀数组，那么满足 \(\operatorname{LCP}(i,c) \ge \operatorname{len}\) 的 \(i\) 构成一个连续的区间

这个可以通过在 \(c\) 两侧二分，每次检查 \(\displaystyle\min_{l + 1 \le k \le r}\{ \operatorname{height} k\}\) 得到（显然这个东西是可以用 ST 表维护的）。

那么现在只需要判断，这个区间中是否有一个 \(i\) 满足 \(\operatorname{sa}(i) \in [a, b - \mathrm{len} + 1]\) 即可。

这个问题等价于：有一个序列，询问一段区间内有多少个数在 \([a, b - \mathrm{len} + 1]\) 之间。

考虑对 sa 数组构建可持久化权值线段树（主席树），每次用第 \(R\) 棵树减去第 \(L-1\) 棵树即可。

时间复杂度 \(\mathcal{O}(n \log n + m \log^2 n)\) ，空间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define ls(at) tr[at].ls
#define rs(at) tr[at].rs
#define mem(a) memset(a, 0, sizeof(a))
#define chk(i, w) (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + w] == tmp[sa[i - 1] + w])

char s[N];
struct node { int ls, rs, sum; } tr[N * 32];
int tot, lg[N], st[18][N], rt[N];
int n, sa[N], rk[N * 2], tmp[N * 2], height[N], cnt[N];
void sort(const int m, int w)
{
    memset(cnt, 0, sizeof(int) * (m + 5));
    for(int i = 1; i <= n; i++) tmp[i] = sa[i];
    for(int i = 1; i <= n; i++) ++cnt[rk[tmp[i] + w]];
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for(int i = n; i; i--) sa[cnt[rk[tmp[i] + w]]--] = tmp[i];
}
void getheight()
{
    int k = 0;
    for(int i = 1; i <= n; height[rk[i]] = k, i++)
    {
        const int j = sa[rk[i] - 1]; if(k) --k;
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
    }
}
void getsa()
{
    const int m = max(n, 233);
    for(int i = 1; i <= n; i++) { sa[i] = i, rk[i] = s[i]; }
    for(int w = 1; w < n; w *= 2)
    {
        sort(m, w); sort(m, 0);
        for(int i = 1; i <= n; i++) tmp[i] = rk[i];
        for(int i = 1, p = 0; i <= n; i++)
            if(chk(i, w)) rk[sa[i]] = p; else rk[sa[i]] = ++p;
    }
}
void buildST()
{
    for(int i = 2; i <= n + 5; i++) lg[i] = lg[i >> 1] + 1;
    for(int i = 2; i <= n; i++) st[0][i] = height[i];
    for(int i = 1; i <= lg[n]; i++)
    {
        int *f = st[i], *g = st[i - 1];
        for(int j = 1; j + (1 << i) - 1 <= n; j++)
            down(f[j] = g[j], g[j + (1 << (i - 1))]);
    }
}
int query(int l, int r)
{
    if(l == r) return INF;
    int k = lg[r - l];
    return min(st[k][l + 1], st[k][r - (1 << k) + 1]);
}
int build(int l, int r)
{
    int at = ++tot;
    if(l < r)
    {
        int mid = (l + r) >> 1;
        ls(at) = build(l, mid);
        rs(at) = build(mid + 1, r);
    }
    return at;
}
int update(int pre, int l, int r, int x)
{
    int at = ++tot; tr[at] = tr[pre]; ++tr[at].sum;
    if(l < r)
    {
        int mid = (l + r) >> 1;
        if(x <= mid) ls(at) = update(ls(pre), l, mid, x);
        else rs(at) = update(rs(pre), mid + 1, r, x);
    }
    return at;
}
int qry(int rt1, int rt2, int l, int r, int nl, int nr)
{
    if(nl <= l && r <= nr) return tr[rt2].sum - tr[rt1].sum;
    int mid = (l + r) >> 1, res = 0;
    if(nl <= mid) res += qry(ls(rt1), ls(rt2), l, mid, nl, nr);
    if(nr > mid) res += qry(rs(rt1), rs(rt2), mid + 1, r, nl, nr);
    return res;
}
bool check(int len, int a, int b, int c)
{
    int l = 1, r = rk[c], L, R;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        query(mid, rk[c]) < len ? l = mid + 1 : r = mid;
    }
    L = l; l = rk[c], r = n;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        query(rk[c], mid) < len ? r = mid - 1 : l = mid;
    }
    R = l;
    return qry(rt[L - 1], rt[R], 1, n, a, b - len + 1) > 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int q; cin >> n >> q >> (s + 1);
    getsa(); getheight(); buildST(); rt[0] = build(1, n);
    for(int i = 1; i <= n; i++) rt[i] = update(rt[i - 1], 1, n, sa[i]); // 全是板子
    for(int i = 1, a, b, c, d; i <= q; i++)
    {
        cin >> a >> b >> c >> d;
        int l = 0, r = min(b - a + 1, d - c + 1);
        while(l < r)
        {
            int mid = (l + r + 1) >> 1;
            check(mid, a, b, c) ? l = mid : r = mid - 1;
        }
        cout << l << '\n';
    }
    return 0;
}