题解 P2336 【[SCOI2012]喵星球上的点名】

· · 题解

一种后缀数组＋树状数组的做法

把所有串串起来建后缀数组，对于每个询问串首向左向右二分找合法区间，

问题就转化成求每个区间包含多少种颜色，和每种颜色被多少区间包含

都可以用树状数组做

对于第一问，可以参考P1972 HH的项链https://www.luogu.org/problemnew/solution/P1972

对于第二问，跟第一问的思路差不多，都是对序列遍历一遍，在区间的左右端点L,R，以及当前点和与当前点同色的上一个点pre[i],i的操作．

第二问是访问到L处给树状数组bit[L]++,到R时bit[L]--,到i时查询sum(i)-sum(pre[i])， 和第一问相反

网上有也一篇博客是这样的做法，讲得更清楚https://blog.csdn.net/kscla/article/details/73176183

总复杂度是O(nlogn)的

代码很丑

#include<bits/stdc++.h>
using namespace std;
const int N=501005,INF=1e9+7;
int nn,q,n,m=N-1000,sa[N],ra[N],h[N],t[N],t1[N],t2[N];
int st[19][N],lg[N];
int s[N],col[N],hd[N],len[N],bu[N];
int pre[N],bit1[N],bit2[N],ans1[N],ans2[N];
int lp[N];//询问区间的左端点
struct P { int id,l,r; } p[N];
bool Cmp(const P &A,const P &B) { return A.r<B.r; }
//后缀数组是之前写的板子，连缩进都不一样
void Getsa() {
  int *x=t1,*y=t2;
  for (int i=1;i<=n;++i) ++t[x[i]=s[i]];
  for (int i=1;i<=m;++i) t[i]+=t[i-1];
  for (int i=n;i;--i) sa[t[x[i]]--]=i;
  for (int k=1;k<=n;k<<=1) {
    int p=0; memset(t,0,m+1<<2);
    for (int i=n-k+1;i<=n;++i) y[++p]=i;
    for (int i=1;i<=n;++i) if (sa[i]>k) y[++p]=sa[i]-k;
    for (int i=1;i<=n;++i) ++t[x[y[i]]];
    for (int i=1;i<=m;++i) t[i]+=t[i-1];
    for (int i=n;i;--i) sa[t[x[y[i]]]--]=y[i];
    swap(x,y); x[sa[1]]=1;
    for (int i=2;i<=n;++i) x[sa[i]]=x[sa[i-1]]+
        (y[sa[i]]!=y[sa[i-1]]||y[sa[i]+k]!=y[sa[i-1]+k]);
    if ((m=x[sa[n]])>=n) break;
  }
}
void Geth() {
  for (int i=1;i<=n;++i) ra[sa[i]]=i;
  for (int i=1,k=0;i<=n;++i) {
    if (k) --k;
    int j=sa[ra[i]-1];
    while (s[i+k]==s[j+k]) ++k;
    h[ra[i]]=k;
  }
}
void Init() {
  for (int i=1;i<=n;++i) st[0][i]=h[i];
  for (int i=1;i<19;++i)
    for (int j=1;j+(1<<i)-1<=n;++j)
      st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i-1)]);
  for (int i=1;(1<<i)<=n;++i) lg[1<<i]=i;
  for (int i=1;i<=n;++i) if (!lg[i]) lg[i]=lg[i-1];
}
int Getmin(int a,int b) {
  if (a==b) return INF;
  if (a>b) swap(a,b);
  int d=lg[b-(a++)];
  return min(st[d][a],st[d][b-(1<<d)+1]);
}
void Upd(int *A,int i,int v) {
    if (i) for (;i<=n;i+=i&-i) A[i]+=v;
}
int Query(int *A,int i) {
    int res=0;
    for (;i;i-=i&-i) res+=A[i];
    return res;
}
void Input() {
    int x,c=1e4;
    scanf("%d%d",&nn,&q);
    for (int i=1;i<=nn;++i) {
        for (int j=0;j<2;++j) {
            scanf("%d",&x);
            while (x--) col[++n]=i,scanf("%d",s+n);
            s[++n]=++c;
        }
    }
    for (int i=1;i<=q;++i) {
        scanf("%d",&len[n+1]); hd[n+1]=i;
        for (int j=len[n+1];j--;) col[++n]=-i,scanf("%d",s+n);
        s[++n]=++c;
    }
}
//同时求出pre[]和询问区间
void Getpre() {
    for (int i=1;i<=n;++i) {
        if (col[sa[i]]>0) {
            pre[i]=bu[col[sa[i]]];
            bu[col[sa[i]]]=i;
        }
        if (hd[i]) {
            p[hd[i]].id=hd[i];
            int l=1,r=ra[i];
            while (l<r) { int mi=l+r>>1; if (Getmin(mi,ra[i])>=len[i]) r=mi; else l=mi+1; }
            p[hd[i]].l=lp[hd[i]]=l;
            l=ra[i],r=n;
            while (l<r) { int mi=l+r+1>>1; if (Getmin(ra[i],mi)>=len[i]) l=mi; else r=mi-1; }
            p[hd[i]].r=r;
        }
    }
    sort(p+1,p+q+1,Cmp);
    sort(lp+1,lp+q+1);
}
//两个询问放到一起做了
void Getans() {
    for (int i=1,j=1,k=1;i<=n;++i) {
        for (;j<=q&&lp[j]==i;++j) Upd(bit2,i,1);
        if (col[sa[i]]>0) {
            ans2[col[sa[i]]]+=Query(bit2,i)-Query(bit2,pre[i]);
            Upd(bit1,i,1); Upd(bit1,pre[i],-1);
        }
        for (;k<=q&&p[k].r==i;++k) {
            ans1[p[k].id]=Query(bit1,p[k].r)-Query(bit1,p[k].l-1);
            Upd(bit2,p[k].l,-1);
        }
    }
}
int main() {
    Input(),Getsa(),Geth(),Init(),Getpre(),Getans();
    for (int i=1;i<=q;++i) printf("%d\n",ans1[i]);
    for (int i=1;i<=nn;++i) printf("%d ",ans2[i]);
}