[后缀数组][二分][莫队]luogu P2336 [SCOI2012]喵星球上的点名

题面

https://www.luogu.com.cn/problem/P2336

分析

先把姓名串在一起做后缀数组，注意各串之间要用不同的分隔符

然后对于每个读入的询问，二分确定它在排好序的后缀上可选的一段区间

接下来这种区间求不同元素出现次数的问题就是经典莫队了

求某元素出现次数，在莫队的时候做差分即可

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=2e5+10;
struct Task {
    int l,r,id;
}t[N];
int n,m,ans1[N],ans2[N],sum;
int s[N],sn,cut=10001,sa[N],x[N],y[N],c[N],d[N],a[N],bel[N],cnt;

void Suffix_Array(int n) {
    int m=cut,cnt=0;
    for (int i=0;i<=m;i++) c[i]=0;
    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=n;i;i--) sa[c[x[i]]--]=i;
    for (int j=1;j<=n;j<<=1) {
        cnt=0;
        for (int i=n-j+1;i<=n;i++) y[++cnt]=i;
        for (int i=1;i<=n;i++) if (sa[i]>j) y[++cnt]=sa[i]-j;
        for (int i=0;i<=m;i++) c[i]=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;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;
        swap(x,y);cnt=x[sa[1]]=1;
        for (int i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[min(sa[i]+j,n+1)]==y[min(sa[i-1]+j,n+1)]?cnt:++cnt);
        m=cnt;if (n==m) break;
    }
}

bool CMP(Task a,Task b) {return bel[a.l]<bel[b.l]||bel[a.l]==bel[b.l]&&((bel[a.l]&1)?a.r<b.r:a.r>b.r);}

void Add(int x,int i) {x=sa[x];if (d[a[x]]++==0) sum++,ans2[a[x]]+=cnt-i+1;}

void Del(int x,int i) {x=sa[x];if (--d[a[x]]==0) sum--,ans2[a[x]]-=cnt-i+1;}

int main() {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        for (int j=0,l;j<2;j++,s[++sn]=++cut) for (scanf("%d",&l);l;l--) ++sn,scanf("%d",&s[sn]),a[sn]=i;
    Suffix_Array(sn);
    for (int i=1,k,p,b,ll,rr,l,r;i<=m;i++) {
        ll=1;rr=sn;p=0;
        for (scanf("%d",&k);k;k--,p++) {
            scanf("%d",&b);
            l=ll;r=rr;
            while (l<=r) {
                int mid=l+r>>1;
                if (s[sa[mid]+p]<b) ll=l=mid+1; else r=mid-1;
            }
            l=ll;r=rr;
            while (l<=r) {
                int mid=l+r>>1;
                if (s[sa[mid]+p]>b) rr=r=mid-1; else l=mid+1;
            }    
        }
        if (ll<=rr) t[++cnt]=(Task){ll,rr,i};
    }
    for (int i=1,j=sqrt(sn);i<=sn;i++) bel[i]=(i-1)/j+1;
    sort(t+1,t+cnt+1,CMP);
    for (int i=1,l=1,r=0;i<=cnt;i++) {
        while (t[i].l<l) Add(--l,i);while (t[i].r>r) Add(++r,i);
        while (t[i].l>l) Del(l++,i);while (t[i].r<r) Del(r--,i);
        ans1[t[i].id]=sum;
    }
    for (int i=1;i<=m;i++) printf("%d
",ans1[i]);
    for (int i=1;i<=n;i++) printf("%d ",ans2[i]);
}