题目链接

BZOJ2754

Luogu2336

概述

本题解法众多，比如：

• AC 自动机

• 广义后缀自动机

• 后缀数组 + 莫队

• ......

这里我介绍一种新的解法：后缀数组 + ST 表 + 二分 + 主席树 + 树状数组。

算法分析

以下是预处理的过程：

• 把所有的姓/名/询问字符串拼接在一起，之间用一个大数作为分隔符隔开，得到新的字符串 a ；

• 记录 a 的第 i 个字符属于猫 b[i] 的名字，若这个字符是分隔符或询问字符串则 b[i]=0 ；再记录第 i 个询问字符串的长度 len[i] ，它的第一个字符在 a 中的位置为 fir[i] ；

• 对 a 进行后缀排序，得到 sa 数组和 rank 数组，并求出 a 的 height 数组， height[i] 表示排名第 i 的后缀与排名第 i-1 的后缀的最长公共前缀的长度（LCP）；

• 根据 height 数组建立 ST表 ，这样可以 O(1) 求出任意两个后缀的 LCP （LCP Theorem ： LCP(i, j)=\underset{ rank[i]<k \leq rank[j] }{ min } \; height[k]）；

• 这样，所以与询问 i 的最长公共前缀大于等于 len[i] 的后缀就一定分布在 rank[fir[i]] 的前后，我们需要在前后各二分一次，求出这个范围 [lef[i], righ[i]] ，则在这个范围内的后缀都能满足询问 i 。

下面进入求解过程：

• 对于第一问，把每一个 b[sa[i]] 视为一种颜色，可以将其转化为求一个区间内不同颜色种数的问题，这个问题可以用 主席树 解决：插入第 i 个数时，把第 i 个版本的主席树的第 i 个位置在第 i-1 个版本的基础上 +1 ，在上一次出现的同种颜色的位置（这里记作 pre[b[sa[i]]]）上 -1 ，以保证只统计每种颜色的最后一次出现；最后处理询问 i 时查询第 righ[i] 个版本的主席树的 [lef[i], righ[i]] 的权值和即可。

• 对于第二问，相当于求每一个颜色被多少个不同的区间覆盖，也就是求每个颜色在区间内第一次出现的次数之和，转换成数学公式就是求满足 l \leq i \leq r, l > pre[b[sa[i]]] 的区间个数（这里解释一下， l>pre[b[sa[i]]] 就表示这个颜色上一次出现的位置在此区间之外，也就是说这个颜色在此区间内是第一次出现），以上条件也可转化为 pre[b[sa[i]]] < l \leq i,r \geqslant i ，可以用解二维偏序的方法求解，简单地对区间右端点进行排序，一边扫描线一边用树状数组记录区间左端点即可。

代码实现

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min;
using std::sort;
const int MAXN=440000;
const int MAXB=20;
const int MAXS=1E4;
int n, m, l;
int a[MAXN], b[MAXN];
int len[MAXN], fir[MAXN];
int sa[MAXN], rank[MAXN*2], rank1[MAXN];
int count[MAXN], tmp[MAXN], height[MAXN];
int lef[MAXN], righ[MAXN];
int root[MAXN], pre[MAXN], ans[MAXN];
struct Interval
{
    int l, r;
    bool operator < (const Interval& rhs) const
    {
        return r<rhs.r;
    }
} d[MAXN];
struct RMQ
{
    int lg[MAXN], st[MAXN][MAXB];
    void build(int* a)
    {
        for (int i=1, k=0; i<=l; i++) lg[i]=1<<k+1==i?++k:k;
        for (int i=1; i<=l; i++) st[i][0]=a[i];
        for (int j=1; 1<<j<=l; j++)
            for (int i=1; i+(1<<j)-1<=l; i++)
                st[i][j]=min(st[i][j-1], st[i+(1<<j-1)][j-1]);
    }
    int lcp(int l, int r)
    {
        int k=lg[r-l];
        return min(st[l+1][k], st[r-(1<<k)+1][k]);
    }
} st;
struct PersistableSegmentTree
{
    struct Node
    {
        int val, lc, rc;
    } tr[MAXN<<5];
    int cnt;
    void pushup(int x)
    {
        tr[x].val=tr[tr[x].lc].val+tr[tr[x].rc].val;
    }
    void insert(int& x, int y)
    {
        tr[x=++cnt]=tr[y];
    }
    void update(int& x, int y, int l, int r, int p, int k)
    {
        insert(x, y);
        if (l==r) { tr[x].val+=k; return; }
        int mid=l+r>>1;
        if (p<=mid) update(tr[x].lc, tr[y].lc, l, mid, p, k);
        else update(tr[x].rc, tr[y].rc, mid+1, r, p, k);
        pushup(x);
    }
    int query(int x, int l, int r, int ql, int qr)
    {
        if (l>qr||r<ql) return 0;
        if (ql<=l&&r<=qr) return tr[x].val;
        int mid=l+r>>1;
        return query(tr[x].lc, l, mid, ql, qr)
              +query(tr[x].rc, mid+1, r, ql, qr);
    }
} pst;
struct BinaryIndexedTree
{
    #define lb(x) (x&-(x))
    int s[MAXN];
    void add(int x, int k)
    {
        while (x<=l) s[x]+=k, x+=lb(x);
    }
    int sum(int x)
    {
        int res=0;
        while (x>0) res+=s[x], x-=lb(x);
        return res;
    }
    #undef lb
} bit;
int getstr(int id)
{
    static int cnt=0;
    int k; scanf("%d", &k);
    for (int i=1; i<=k; i++)
        scanf("%d", &a[++l]), b[l]=id;
    a[++l]=MAXS+(++cnt);
    return k;
}
int main()
{
//  freopen("bzoj2754.in", "r", stdin);
//  freopen("bzoj2754.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++) getstr(i), getstr(i);
    // 当前询问字符串末尾的分隔符位置为 l ，则此字符串的起始位置就是 l-len[i]
    for (int i=1; i<=m; i++) len[i]=getstr(0), fir[i]=l-len[i];
    // 以下是后缀排序
    memset(count, 0, sizeof count);
    memset(rank, 0, sizeof rank);
    for (int i=1; i<=l; i++) count[a[i]]=1;
    for (int i=1; i<MAXN; i++) count[i]+=count[i-1];
    for (int i=1; i<=l; i++) rank[i]=count[a[i]];
    for (int p=1, k=0; k!=l; p<<=1)
    {
        memset(count, 0, sizeof count);
        for (int i=1; i<=l; i++) count[rank[i+p]]++;
        for (int i=1; i<=l; i++) count[i]+=count[i-1];
        for (int i=l; i>=1; i--) tmp[count[rank[i+p]]--]=i;
        memset(count, 0, sizeof count);
        for (int i=1; i<=l; i++) count[rank[i]]++;
        for (int i=1; i<=l; i++) count[i]+=count[i-1];
        for (int i=l; i>=1; i--) sa[count[rank[tmp[i]]]--]=tmp[i];
        memcpy(rank1, rank, sizeof rank1);
        rank[sa[1]]=k=1;
        for (int i=2; i<=l; i++)
        {
            if (rank1[sa[i]]!=rank1[sa[i-1]]
              ||rank1[sa[i]+p]!=rank1[sa[i-1]+p]) k++;
            rank[sa[i]]=k;
        }
    }
    // 求 height 数组
    for (int i=1, k=0; i<=l; i++)
    {
        if (rank[i]==1)
        {
            height[rank[i]]=k=1;
            continue;
        }
        if (--k<0) k=0;
        while (a[i+k]==a[sa[rank[i]-1]+k]) k++;
        height[rank[i]]=k;
    }
    // 建立 st 表
    st.build(height);
    for (int i=1; i<=m; i++)
    {
        lef[i]=righ[i]=rank[fir[i]];
        for (int j=MAXB-1; j>=0; j--)
            if (lef[i]-(1<<j)>=1&&st.lcp(lef[i]-(1<<j), rank[fir[i]])>=len[i])
                lef[i]-=1<<j;
        for (int j=MAXB-1; j>=0; j--)
            if (righ[i]+(1<<j)<=l&&st.lcp(rank[fir[i]], righ[i]+(1<<j))>=len[i])
                righ[i]+=1<<j;
        d[i].l=lef[i]; d[i].r=righ[i];
    }
    // 做了一份所有区间的备份数组 d ，并对 d 按右端点从小到大排序
    sort(d+1, d+m+1);
    // 先把树状数组中所有的左端点的权值都赋为 +1
    for (int i=1; i<=m; i++) bit.add(d[i].l, 1);
    memset(pre, 0, sizeof pre);
    for (int i=1, j=1; i<=l; i++)
        // 如果这个位置是分隔符或询问字符串，直接复制一个和上个版本一样的主席树
        if (b[sa[i]]==0) pst.insert(root[i], root[i-1]);
        else
        {
            if (!pre[b[sa[i]]]) pst.update(root[i], root[i-1], 1, l, i, 1);
            else
            {
                int temp;
                // 先在该颜色上一次出现的位置上 -1
                pst.update(temp, root[i-1], 1, l, pre[b[sa[i]]], -1);
                // 然后在当前位置上 +1
                pst.update(root[i], temp, 1, l, i, 1);
            }
            // 所有右端点小于 i 的区间都不符合要求了，从将其左端点在树状数组中 -1
            while (j<=m&&d[j].r<i) bit.add(d[j++].l, -1);
            // 左端点属于 [pre[b[sa[i]]]+1, i] 的计入答案
            ans[b[sa[i]]]+=bit.sum(i)-bit.sum(pre[b[sa[i]]]);
            // 更新 pre
            pre[b[sa[i]]]=i;
        }
    // 在主席树中查询
    for (int i=1; i<=m; i++)
        printf("%d\n", pst.query(root[righ[i]], 1, l, lef[i], righ[i]));
    for (int i=1; i<=n; i++) printf("%d ", ans[i]); putchar('\n');
    return 0;
}