bzoj 2754 [SCOI2012]喵星球上的點名 字尾數組+莫隊

先把所有串按順序放到一起，兩個串間加非法字元隔開，求一個字尾數組。

然後對于詢問，滿足條件的子串在字尾數組上一定是連續一段區間。

這個區間的左右端點可以在讀入的過程中二分求。

然後這個問題變成了多組詢問求一段區間内不同的數的個數。

莫隊裸題。

慢着，每個元素的出現次數怎麼求呀？

莫隊時維護，設共有cnt個詢問，那麼第i個詢問時一個元素的出現狀态的改變會影響到cnt-i+1個詢問中該元素的出現狀态。是以答案累加相應次數就行了。

#include <bits/stdc++.h>
using namespace std;
#define N 210000
#define A 11000
int n,m,len,cnt,sz;
int a[N],bel[N],sa[N],has[N],tr[N],rank[N],ans[N];
int num[N],sum,a1[N];
int cmp(int x,int y,int k)
{
    if(x+k>len||y+k>len)return ;
    return rank[x]==rank[y]&&rank[x+k]==rank[y+k];
}
void getsa()
{
    int i,cnt;
    for(i=;i<=len;i++)has[a[i]]++;
    for(i=,cnt=;i<=A;i++)if(has[i])tr[i]=++cnt;
    for(i=;i<=A;i++)has[i]+=has[i-];
    for(i=;i<=len;i++)rank[i]=tr[a[i]],sa[has[a[i]]--]=i;
    for(int k=;cnt!=len;k<<=)
    {
        for(i=;i<=len;i++)has[i]=;
        for(i=;i<=len;i++)has[rank[i]]++;
        for(i=;i<=len;i++)has[i]+=has[i-];
        for(i=len;i>=;i--)if(sa[i]>k)tr[sa[i]-k]=has[rank[sa[i]-k]]--;
        for(i=;i<=k;i++)tr[len-i+]=has[rank[len-i+]]--;
        for(i=;i<=len;i++)sa[tr[i]]=i;
        for(i=,cnt=;i<=len;i++)tr[sa[i]]=cmp(sa[i],sa[i-],k) ? cnt:++cnt;
        for(i=;i<=len;i++)rank[i]=tr[i];
    }
}
struct node
{
    int l,r,pos;
    node(){}
    node(int l,int r,int pos):l(l),r(r),pos(pos){}
    friend bool operator < (const node &r1,const node &r2)
    {
        if(r1.l/sz==r2.l/sz)return r1.r<r2.r;
        return r1.l/sz<r2.l/sz;
    };
}p[N];
void insert(int x,int tp,int now)
{
    int t=bel[sa[x]];
    num[t]+=tp;
    if(tp==&&num[t]==)sum++,a1[t]+=(cnt-now+);
    if(tp==-&&num[t]==)sum--,a1[t]-=(cnt-now+);
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=,l;i<=n;i++)
        for(int j=;j<=;j++)
        {
            scanf("%d",&l);
            for(int k=;k<=l;k++)
                scanf("%d",&a[++len]),bel[len]=i;
            a[++len]=A;
        }
    sz=sqrt(len)+;
    getsa();
    for(int n1,now=;now<=m;now++)
    {
        scanf("%d",&n1);
        int ln=,rn=len;
        for(int i=,x;i<=n1;i++)
        {
            scanf("%d",&x);
            int l=ln,r=rn,lt;
            while(l<=r)
            {
                int mid=(l+r)>>;
                if(a[sa[mid]+i-]<x)l=mid+;
                else r=mid-;
            }
            lt=l;l=ln,r=rn;
            while(l<=r)
            {
                int mid=(l+r)>>;
                if(a[sa[mid]+i-]<=x)l=mid+;
                else r=mid-;
            }
            rn=r;ln=lt;
        }
        if(ln<=rn)p[++cnt]=node(ln,rn,now);
    }
    sort(p+,p++cnt);
    for(int i=,l=,r=;i<=cnt;i++)
    {
        while(l<p[i].l)insert(l,-,i),l++;
        while(l>p[i].l)l--,insert(l,,i);
        while(r<p[i].r)r++,insert(r,,i);
        while(r>p[i].r)insert(r,-,i),r--;
        ans[p[i].pos]=sum;
    }
    for(int i=;i<=m;i++)
        printf("%d\n",ans[i]);
    for(int i=;i<=n;i++)
        printf("%d%c",a1[i],i==n ? '\n':' ');
    return ;
}