迷惑
查看原帖
迷惑
142067
wind_cross楼主2021/12/11 12:27

不开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;
}
2021/12/11 12:27
加载中...