不开O2毫无问题,开了O2就全wa而且输出0之类的,感觉出现了一些奇怪问题,求查错……
#include<cstdio>
#include<cctype>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;
inline char nc()
{
static char buf[99999],*l,*r;
return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
template <class code>inline code read(const code &a)
{
code x=0;short w=0;char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return w?-x:x;
}
void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>=10)print(x/10);
putchar(x%10+48);
}
struct pp{
int be;
int en;
int rank;
}sc[400005];
vector<int>ws[400005];
int sa[1000005],cc[400005],m=10000,n,jl[1000005],ra[1000005],a[1000005],q,be[100005],en[100005],wz[100005],zz[400005],he[400005],st[19][400005],lg[400005],qz[400005],pl[400005],id[400005],h[400005],cnt,pre[400005];
int cx(int x,int y){
if(x>y)return 0;
int sj=lg[y-x+1];
return min(st[sj][x],st[sj][y-(1<<sj)+1]);
}
int lowbit(int x){return x&(-x);}
void update(int x,int v){
for(int i=x;i<=cnt;i+=lowbit(i))h[i]+=v;
}
int cx(int x){
int su=0;
for(int i=x;i>0;i-=lowbit(i))su+=h[i];
return su;
}
bool cmp(pp x,pp y){
return x.en<y.en;
}
bool cmp1(pp x,pp y){
return x.be<y.be;
}
signed main()
{
//freopen("测试.in","r",stdin);
//freopen("测试.out","w",stdout);
n=read(n),q=read(q);
cnt=0;
for(int i=1;i<=n;i++){
int l=read(l);
for(int j=1;j<=l;j++){
int x=read(x);
a[++cnt]=x;
id[cnt]=i;
}
++m;
a[++cnt]=m;
l=read(l);
for(int j=1;j<=l;j++){
int x=read(x);
a[++cnt]=x;
id[cnt]=i;
}
++m;
a[++cnt]=m;
}
for(int i=1;i<=q;i++){
int l=read(l);
pl[i]=l;
wz[i]=cnt+1;
for(int j=1;j<=l;j++){
int x=read(x);
a[++cnt]=x;
}
++m;
a[++cnt]=m;
}
lg[1]=0;
for(int i=2;i<=cnt;i++)lg[i]=lg[i/2]+1;
for(int i=1;i<=cnt;i++)++jl[ra[i]=a[i]];
for(int i=1;i<=m;i++)jl[i]+=jl[i-1];
for(int i=cnt;i>=1;i--)sa[jl[ra[i]]--]=i;
for(int j=1;j<=cnt;j<<=1){
int qwq=0;
for(int i=cnt-j+1;i<=cnt;i++)zz[++qwq]=i;
for(int i=1;i<=cnt;i++){
if(sa[i]>j)zz[++qwq]=sa[i]-j;
}
memset(jl,0,sizeof(jl));
for(int i=1;i<=cnt;i++)jl[ra[i]]++;
for(int i=1;i<=m;i++)jl[i]+=jl[i-1];
for(int i=cnt;i>=1;i--)sa[jl[ra[zz[i]]]--]=zz[i];
memcpy(zz,ra,sizeof(ra));
for(int i=1;i<=cnt;i++){
ra[sa[i]]=(zz[sa[i]]==zz[sa[i-1]]&&zz[sa[i]+j]==zz[sa[i-1]+j])?ra[sa[i-1]]:ra[sa[i-1]]+1;
}
m=ra[sa[cnt]];
if(ra[sa[cnt]]==cnt)break;
}
int mq=0;
for(int i=1;i<=cnt;i++){
if(ra[i]==1)continue;
if(mq)--mq;
int j=sa[ra[i]-1];
while(i+mq<=cnt&&j+mq<=cnt&&a[i+mq]==a[j+mq])++mq;
he[ra[i]]=mq;
st[0][ra[i]]=mq;
}
for(int i=1;i<=18;i++){
for(int j=1;j+(1<<i)-1<=cnt;j++){
st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
}
for(int i=1;i<=q;i++){
int kx=ra[wz[i]];
int zl=1,zr=kx-1,fs=kx;
while(zl<=zr){
int mid=(zl+zr)>>1;
if(cx(mid+1,kx)>=pl[i])fs=mid,zr=mid-1;
else zl=mid+1;
}
sc[i].be=fs;
zl=kx+1,zr=cnt,fs=kx;
while(zl<=zr){
int mid=(zl+zr)>>1;
if(cx(kx+1,mid)>=pl[i])fs=mid,zl=mid+1;
else zr=mid-1;
}
sc[i].en=fs;
sc[i].rank=i;
}
sort(sc+1,sc+q+1,cmp);
for(int i=1;i<=q;i++){
for(int j=sc[i-1].en+1;j<=sc[i].en;j++){
if(id[sa[j]]>0){
if(pre[id[sa[j]]]>0)update(pre[id[sa[j]]],-1);
be[j]=pre[id[sa[j]]];
pre[id[sa[j]]]=j;
update(j,1);
}
}
zz[sc[i].rank]=cx(sc[i].en)-cx(sc[i].be-1);
}
for(int i=1;i<=q;i++)printf("%d\n",zz[i]);
memset(h,0,sizeof(h));
memset(zz,0,sizeof(zz));
sort(sc+1,sc+q+1,cmp1);
for(int i=1;i<=q;i++)ws[sc[i].en].push_back(sc[i].be);
int wz=1;
for(int i=1;i<=cnt;i++){
while(sc[wz].be==i)update(i,1),++wz;
if(id[sa[i]]>0){
zz[id[sa[i]]]+=cx(i)-cx(be[i]);
}
for(int j=0;j<ws[i].size();j++)update(ws[i][j],-1);
}
for(int i=1;i<=n;i++)printf("%d ",zz[i]);
puts("");
return 0;
}