Luogu P2336 [SCOI2012]喵星球上的点名

题解：二分+莫队

感谢hl666大佬

我们搞出后缀数组然后对于每一个询问串二分出在后缀数组上对应的询问区间。

然后我们的问题变成了区间颜色数，即不同种类的后缀数，开个桶即可。

如何考虑对每只猫的贡献？比如总询问数为 \(cnt\) ，有一只猫待在桶里的时间为 \([i,j)\) 。我们可以先假设猫能在桶里一直待到最后，在答案数组中加上 \(cnt-i+1\)。当把猫从桶里拎出来时减掉 \(cnt-j+1\)即可。

#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define R register int
using namespace std;
namespace Luitaryi {
char D[1<<23],*S=D,*E=D;
#define getchar() (S==E && (E=(S=D)+fread(D,1,1<<23,stdin),S==E)?EOF:*S++)
inline int g() { R x=0,f=1;
  register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;
  do x=x*10+(s-48); while(isdigit(s=getchar())); return x*f;
} const int N=200010;
int T,n,m,cnt,tot,B,L,a[N],pos[N],be[N],d[N];
int sa[N],rk[N],ht[N],c[N],x[N],y[N],ans[N],anss[N];
struct node {
  int l,r,id;
  inline bool operator < (const node& that) const 
    {return be[l]==be[that.l]?(be[l]&1?r<that.r:r>that.r):l<that.l;}
}q[N];
inline void pre() {
  R m=L;
  for(R i=1;i<=n;++i) ++c[x[i]=a[i]];
  for(R i=1;i<=m;++i) c[i]+=c[i-1];
  for(R i=n;i;--i) sa[c[x[i]]--]=i;
  for(R t=1,top=0;top<n;m=top,t<<=1) {
    top=0;
    for(R i=n-t+1;i<=n;++i) y[++top]=i;
    for(R i=1;i<=n;++i) if(sa[i]>t) y[++top]=sa[i]-t;
    memset(c,0,(m+1)<<2);
    for(R i=1;i<=n;++i) ++c[x[i]];
    for(R i=1;i<=m;++i) c[i]+=c[i-1];
    for(R i=n;i;--i) sa[c[x[y[i]]]--]=y[i];
    swap(x,y),x[sa[1]]=top=1;
    for(R i=2;i<=n;++i) 
      x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+t]==y[sa[i-1]+t])?top:++top;
  } for(R i=1;i<=n;++i) rk[sa[i]]=i;
}
inline void add(int x,int p) {
  if(++d[pos[x]]==1) ++tot,anss[pos[x]]+=cnt-p+1;
}
inline void sub(int x,int p) {
  if(--d[pos[x]]==0) --tot,anss[pos[x]]-=cnt-p+1;
}
inline void main() {
  T=g(),m=g(); L=10000;
  for(R i=1,lim=T<<1;i<=lim;++i) {
    for(R j=1,x=g();j<=x;++j) 
      a[++n]=g(),pos[n]=(i+1)>>1;
    a[++n]=++L;
  } B=sqrt(n);
  for(R i=1;i<=n;++i) be[i]=(i-1)/B+1;
  pre();
  for(R i=1,len,LL,RR,flg;i<=m;++i) {
    len=g(),LL=1,RR=n,flg=0;
    for(R j=1,x;j<=len;++j) {
      x=g(); R l=LL,r=RR,md; 
      while(l<r) {
        md=(l+r)>>1;
        if(a[sa[md]+j-1]<x) l=md+1;
        else r=md;
      }
      R tmp=l; l=LL,r=RR;
      while(l<r) {
        md=(l+r+1)>>1;
        if(a[sa[md]+j-1]<=x) l=md;
        else r=md-1;
      }
      LL=tmp,RR=l;
      if(LL==RR && a[sa[LL]+j-1]!=x) flg=true;
    } if(!flg && LL<=RR) q[++cnt]=(node){LL,RR,i};
  }
  sort(q+1,q+cnt+1);
  for(R i=1,l=1,r=0;i<=cnt;++i) {
    R LL=q[i].l,RR=q[i].r;
    while(l>LL) add(sa[--l],i);
    while(r<RR) add(sa[++r],i);
    while(l<LL) sub(sa[l++],i);
    while(r>RR) sub(sa[r--],i);
    ans[q[i].id]=tot;
  } 
  for(R i=1;i<=m;++i) printf("%d\n",ans[i]);
  for(R i=1;i<=T;++i) printf("%d ",anss[i]);
}
} signed main() {Luitaryi::main(); return 0;}

2020.01.09

Luogu P2336 [SCOI2012]喵星球上的点名

原文：https://www.cnblogs.com/Jackpei/p/12177365.html