「SCOI2012」喵星球上的点名题解

2020-01-02

题目链接: https://www.luogu.com.cn/problem/P2336

一道后缀数组的题, 毒瘤了我大半个晚上, 故写题解以纪念.

一些约定

字符串下标从 $1$ 开始
记 $sa[i]$ 表示字符串所有后缀排序后第 $i$ 大的后缀的编号, $rnk[i]$ 表示后缀 $i$ 在 $sa$ 中的下标, 即后缀 $i$ 在所有后缀中的排名

运用到 SA 的性质

SA 中前缀相同的串排在一起, 也就是说, SA 按照字典序对所有后缀排序
两子串最长公共前缀

$\text{LCP}(sa[i], sa[j]) = \min_{k = i+1}^j \{ \text{height[k]} \}$

题解

首先, 我们的任务是确定一个字符串是不是一个字符串的子串, 可以联想到的算法有 AC 自动机, 哈希之类的东西… 不过这道题的字符集大小达到了 $10^4$, 感觉 SA 似乎更可做一点.

那么, 怎么用 SA 确定一个字符串是否是另一个字符串的子串呢? 可以通过 LCP 来做.

现在有一个显然的事情, 如果一个字符串 $S$ 是 $T$ 的子串, 那么 $T$ 存在一个后缀 $T’$, 使得 $\text{LCP}(S, T’) = |S|$.

对于一个 $S$ 和一个 $T$, 可以将 $S, T$ 拼接成一个新串, 中间用一个从未出现过的字符连接, 通过对新串求后缀数组, 然后再二分判定.

回到这道题上来, 对于多个 $S$, $T$, 也可以用相同的方式. 对于一个 “点名串” $S$, 包含 $S$ 的字符串一定在 $sa$ 是一段连续的区间. 那么, 现在的问题就是序列上的问题了.

区间 $[L, R]$ 中不同猫的个数;
询问完之后猫的点名次数.

~~存在使用树状数组 / 线段树的做法, 可惜实在学不会, 于是使用了莫队~~

考虑莫队, 第一个问题比较经典, 开一个桶记录猫在现在维护区间内出现次数, 在出现次数改变为 0 / 1 时更新答案就可以了. 对于第二个问题, 参考了 hl666 的题解 = =, 每次有新的猫进入区间, 或者一只猫已经完全离开现在的区间时, 更新当前情况下被点到次数的最大值.

但是这样为什么是对的呢? 考虑一只猫进出区间的两个过程, 虽然我们在进入区间的时候给他算上了最大的可能点名次数, 但是在离开又减去了可能的最大值. 感性理解一下, 差值就像是正确答案…

代码

写起来 rnk, sa, idx 翻来覆去 = =

// Luogu P2336
// DeP
#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;
// 普通的读入

const int MAXN = 1e6+5, MAXM = 1e4+1;
int block;

struct Ask {
    int idx, L, R;
    bool operator < (const Ask& rhs) const {
        return R / block == rhs.R / block? (L == rhs.L? 0: ((R / block) & 1) & (L < rhs.L)): R < rhs.R;
    }
} Q[MAXN];

int n, N, q;
int A[MAXN];
int S[MAXN]; // 拼接后的数组
int idx[MAXN]; // 拼接后第 i 个位置对应原字符串的编号
int firstpos[MAXN]; // 点名串对应在 S 中的位置, 二分区间左右端点使用
int qlen[MAXN]; // 点名串长度

inline void add(int val, int id) { S[++n] = val, idx[n] = id; } // 更新 S

namespace SA {
    int sa[MAXN], rnk[MAXN], id[MAXN], px[MAXN], ht[MAXN], cnt[MAXN];

    inline bool cmp(const int& x, const int& y, const int& k) {
        return id[x] == id[y] && id[x+k] == id[y+k];
    }

    inline void build(int m) {
        int i, k, p = 0;
        for (i = 1; i <= n; ++i) ++cnt[rnk[i] = S[i]];
        for (i = 1; i <= m; ++i) cnt[i] += cnt[i-1];
        for (i = n; i; --i) sa[cnt[rnk[i]]--] = i;
        for (k = 1; k <= n && p < n; k <<= 1, m = p) {
            for (p = 0, i = n; i > n-k; --i) id[++p] = i;
            for (i = 1; i <= n; ++i) if (sa[i] > k) id[++p] = sa[i]-k;
            memset(cnt, 0, sizeof (int) * (m+1));
            for (i = 1; i <= n; ++i) ++cnt[px[i] = rnk[id[i]]];
            for (i = 1; i <= m; ++i) cnt[i] += cnt[i-1];
            for (i = n; i; --i) sa[cnt[px[i]]--] = id[i]; // 这里打挂过
            swap(rnk, id), rnk[sa[1]] = p = 1;
            for (i = 2; i <= n; ++i) rnk[sa[i]] = cmp(sa[i], sa[i-1], k)? p: ++p;
        }
        for (i = 1; i <= n; ++i) rnk[sa[i]] = i; // 这里打挂过
        for (k = 0, i = 1; i <= n; ++i) {
            if (k) --k;
            while (S[i + k] == S[sa[rnk[i]-1] + k]) ++k;
            ht[rnk[i]] = k;
        }
    }
}
using SA::rnk; using SA::sa;
// SA 倍增实现模板

namespace ST {
    const int LOG = 21;
    int minHt[LOG][MAXN], lg2[MAXN];

    inline void init() {
        for (int i = 1; i <= n; ++i) minHt[0][i] = SA::ht[i];
        for (int j = 1; j < LOG; ++j)
            for (int i = 1; i+(1<<j)-1 <= n; ++i)
                minHt[j][i] = min(minHt[j-1][i], minHt[j-1][i+(1<<(j-1))]);
        lg2[1] = 0;
        for (int i = 2; i <= n; ++i) lg2[i] = lg2[i/2] + 1;
    }

    inline int RMQ(int L, int R) {
        int k = lg2[R-L+1];
        return min(minHt[k][L], minHt[k][R-(1<<k)+1]);
    }
}
// 实现 RMQ

namespace MoAlg {
    int L, R, ans1;
    int Ans1[MAXN], Ans2[MAXN], cnt[MAXN];

    inline void add(int pos, int cur) {
        pos = idx[pos];
        if (pos <= N && ++cnt[pos] == 1) ++ans1, Ans2[pos] += q-cur+1;
        // 只统计编号在猫范围之内的种类数
    }

    inline void del(int pos, int cur) {
        pos = idx[pos];
        if (pos <= N && --cnt[pos] == 0) --ans1, Ans2[pos] -= q-cur+1;
        // 只统计编号在猫范围之内的种类数
    }

    inline void solve() {
        block = int( n / sqrt(q) );
        sort(Q+1, Q+1+q);
        L = 1, R = ans1 = 0;
        for (int i = 1; i <= q; ++i) {
            const Ask& qr = Q[i];
            while (L > qr.L) add(sa[--L], i);
            while (R > qr.R) del(sa[R--], i);
            while (L < qr.L) del(sa[L++], i);
            while (R < qr.R) add(sa[++R], i);
            Ans1[qr.idx] = ans1;
        }
    }
}
using MoAlg::Ans1; using MoAlg::Ans2;
// 莫队

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(N), read(q);
    for (int k, i = 1; i <= N; ++i) {
        read(k);
        for (int j = 1; j <= k; ++j) read(A[j]), add(A[j]+1, i);
        add(MAXM + 2*i-1, N+1);
        read(k);
        for (int j = 1; j <= k; ++j) read(A[j]), add(A[j]+1, i);
        add(MAXM + 2*i, N+1);
    }
    for (int k, i = 1; i <= q; ++i) {
        read(k), qlen[i] = k, firstpos[i] = n+1;
        for (int j = 1; j <= k; ++j) read(A[j]), add(A[j]+1, N + i);
        add(MAXM + 2*N + i, N+1);
    }
    // solve
    SA::build(MAXM + 2*N + q), ST::init();
    for (int i = 1; i <= q; ++i) {
        static int L, R, qL, qR;
        L = 1, R = rnk[firstpos[i]]-1, qL = rnk[firstpos[i]];
        while (L <= R) {
            int Mid = (L + R) / 2;
            // LCP, 注意到 +1
            if (ST::RMQ(Mid + 1, rnk[firstpos[i]]) >= qlen[i]) qL = Mid, R = Mid - 1;
            else L = Mid + 1;
        }
        L = rnk[firstpos[i]]+1, R = n, qR = rnk[firstpos[i]];
        while (L <= R) {
            int Mid = (L + R) / 2;
            // LCP, 注意到 +1
            if (ST::RMQ(rnk[firstpos[i]] + 1, Mid) >= qlen[i]) qR = Mid, L = Mid + 1;
            else R = Mid - 1;
        }
        Q[i] = (Ask){ i, qL, qR };
    }
    MoAlg::solve();
    // output
    for (int i = 1; i <= q; ++i) printf("%d\n", Ans1[i]);
    for (int i = 1; i <= N; ++i) printf("%d%c", Ans2[i], " \n"[i==N]);
    return 0;
}

得出的一些调试的经验?

如果不保证模板的正确性, 先检查以下板子… = =
~~抄题解的时候注意一些细节, 以免调试半天发现是细节问题~~

DepletedPrism's Blog

「SCOI2012」喵星球上的点名 题解

一些约定

运用到 SA 的性质

题解

代码

得出的一些调试的经验?

「SCOI2012」喵星球上的点名题解