Problem

https://www.luogu.org/problemnew/show/P2336

Solution

考虑排序好的询问串左右两边能到达的最远的子串，每个串的 lcp 等于串的长度。

转化为区间问题，一个区间里有多少类数，和一类数被多少个区间包括。

第一问为 HH 的项链，可树状数组处理。
第二问可以不重复的讨论 i 与 lst_i+ 1 之间有多少个 L 到 R 区间包括了 i，同样用树状数组讨论。

代码很丑...

Code

// Code by ajcxsu
// Problem: name on miao star

#include<bits/stdc++.h>
using namespace std;

template<typename T> inline void gn (T &x) {
    char ch=getchar(); x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=4e5+10;
int idx=N>>1;

int x[N], y[N], sa[N], c[N];
int fa[N], xl[N], xr[N], col[N], hei[N], rc[N], pos[N], id[N], lst[N], length[N];
typedef pair<int, int> mpair;
vector<mpair> l[N], r[N];
vector<int> qu[N];
int Find(int x) { return fa[x]?fa[x]=Find(fa[x]):x; }
int Union(int a, int b) {
    int af=Find(a), bf=Find(b);
    fa[af]=bf; xr[bf]=max(xr[bf], xr[af]), xl[bf]=min(xl[bf], xl[af]); return bf;
}
bool cmp(const int &a, const int &b) { return hei[a]>hei[b]; }
int s[N], a1[N], a2[N];
int n, m, len;
void gsa() {
    int n=len, m=N-1;
    for(int i=1;i<=n;i++) c[x[i]=s[i]]++;
    for(int i=1;i<=m;i++) c[i]+=c[i-1];
    for(int i=1;i<=n;i++) sa[c[x[i]]--]=i;
    int num;
    for(int k=1;k<=n;k<<=1) {
        num=0;
        for(int i=n-k+1;i<=n;i++) y[++num]=i;
        for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
        fill(c, c+m+1, 0);
        for(int i=1;i<=n;i++) c[x[i]]++;
        for(int i=1;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i], y[i]=0;
        swap(x, y), x[sa[1]]=1, num=1;
        for(int i=2;i<=n;i++)
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]?num:++num);
        if(num==n) break;
        m=num;
    }
    int k=0, j;
    for(int i=1;i<=n;i++) if(x[i]>1) {
        if(k) k--; j=sa[x[i]-1];
        while(s[j+k]==s[i+k]) k++;
        hei[x[i]]=k;
    }
}

#define lowbit(x) x&-x
int C[N];
void updata(int x, int d) {
    while(x<N) C[x]+=d, x+=lowbit(x);
}
int query(int x) {
    int ret=0; while(x) ret+=C[x], x-=lowbit(x);
    return ret;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    gn(n), gn(m);
    int L, na;
    for(int i=1;i<=n;i++) {
        gn(L);
        for(int j=1;j<=L;j++) gn(na), s[++len]=na, col[len]=i;
        s[++len]=N-2, gn(L);
        for(int j=1;j<=L;j++) gn(na), s[++len]=na, col[len]=i;
        s[++len]=++idx;
    }
    for(int i=1;i<=m;i++) {
        gn(L), col[len+1]=-i, length[i]=L, qu[L].push_back(i), pos[i]=len+1;
        for(int j=1;j<=L;j++) gn(na), s[++len]=na;
        s[++len]=++idx;
    }
    for(int i=1;i<=len;i++) s[i]++;
    gsa();
    for(int i=1;i<=len;i++) xl[i]=xr[i]=i, id[i]=i, rc[i]=col[sa[i]];
    sort(id+1, id+1+len, cmp);
    int xf;
    for(int i=1;i<=len;i++) {
        if(i>1 && hei[id[i]]!=hei[id[i-1]]) {
            for(int j:qu[hei[id[i-1]]]) {
                xf=Find(x[pos[j]]), l[xl[xf]].push_back(mpair(xr[xf], j));
                r[xr[xf]].push_back(mpair(xl[xf], j));
            }
        }
        Union(id[i], id[i]-1);
    }
    for(int i=1;i<=len;i++) {
        if(rc[i]>0) {
            if(lst[rc[i]]) updata(lst[rc[i]], -1);
            updata(i, 1), lst[rc[i]]=i;
        }
        for(auto x:r[i]) a1[x.second]+=query(i)-query(x.first-1);
    }
    for(int i=1;i<=m;i++) printf("%d\n", a1[i]);
    memset(C, 0, sizeof(C)), memset(lst, 0, sizeof(lst));
    for(int i=1;i<=len;i++) {
        updata(i, l[i].size());
        if(rc[i]>0) {
            if(lst[rc[i]]) a2[rc[i]]+=query(i)-query(lst[rc[i]]);
            else a2[rc[i]]+=query(i);
            lst[rc[i]]=i;
        }
        for(auto x:r[i]) updata(x.first, -1);
    }
    for(int i=1;i<=n;i++) printf("%d ", a2[i]);
    putchar('\n');
    return 0;
}