QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#79950#5014. 复读程度NATURAL60 8ms51808kbC++149.2kb2023-02-21 13:38:582023-02-21 13:38:59

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-21 13:38:59]
  • 评测
  • 测评结果:0
  • 用时:8ms
  • 内存:51808kb
  • [2023-02-21 13:38:58]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define N 200010
inline unsigned long long qread()
{
    unsigned long long a=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){(a*=10)+=(ch^48);ch=getchar();}
    return a*f;
}
int n,m,cx,xk,L,R,tot,occ[N],rt[2][N];
int cl=400,l,r,c[N];
unsigned long long wl[N],wr[N],ans[N],vr[N],vl[N];
char ch[N];
struct node
{
    int x,y,id;
    unsigned long long val;
};
bool operator<(const node x,const node y){return x.x==y.x?x.y<y.y:x.x<y.x;}
bool operator>(const node x,const node y){return x.x==y.x?x.y>y.y:x.x>y.x;}
inline bool cmp(node x,node y){return c[x.x]==c[y.x]?((c[x.x]&1)?x.y<y.y:x.y>y.y):x.x<y.x;}
vector<node>q,Q[2][N];
struct E
{
    int tot,head[N],nex[N],t[N];
    inline void adde(int x,int y)
    {
        t[++tot]=y;
        nex[tot]=head[x];
        head[x]=tot;
        return ;
    }
};
struct BIT
{
	int tim,tag[N];
	unsigned long long val[N];
    inline int lowbit(int x){return x&-x;}
	inline void adds(int x,unsigned long long y)
    {
		for(;x<=n*2;x+=lowbit(x))
        {
			(tag[x]!=tim)&&(tag[x]=tim,val[x]=0);
			val[x]+=y;
		}
	}
	unsigned long long ask(int x)
    {
		unsigned long long an=0;
		for(;x;x-=lowbit(x))an+=tag[x]==tim?val[x]:0;
		return an;
	}
}bit;
struct sam
{
    int ps,p,link[N],len[N],tot,cnt,T,siz[N];
    int rg[N],ed[N],c[N],sz[N],pos[N],clen[N];
    int s[N],top[N],dfn[N],rk[N],tag[N];
    vector<int>vec[N];
    map<char,int>ch[N];
    E e;
    inline void addc(char c)
    {
        len[ps=++cnt]=len[p=T]+1,siz[T=ps]=1;
        while(p&&!ch[p][c])ch[p][c]=ps,p=link[p];
        if(!p)return link[ps]=1,void();
        cx=ch[p][c];
        if(len[p]+1==len[cx])return link[ps]=cx,void();
        xk=++cnt;
        len[xk]=len[p]+1;
        ch[xk]=ch[cx];
        rg[xk]=rg[cx];
        link[xk]=link[cx];
        while(p&&ch[p][c]==cx)ch[p][c]=xk,p=link[p];
        link[cx]=link[ps]=xk;
        return ;
    }
    inline void dfs(int rt)
    {
        dfn[rt]=++tot;
        rk[tot]=rt;
        if(s[rt])top[s[rt]]=top[rt],dfs(s[rt]);
        for(int i=e.head[rt];i;i=e.nex[i])
        {
            if(e.t[i]==s[rt])continue;
            top[e.t[i]]=e.t[i];
            dfs(e.t[i]);
        }
        return ;
    }
    inline void init()
    {
        for(int i=1;i<=cnt;++i)++c[len[i]],sz[i]=1;
		for(int i=1;i<=n;++i)c[i]+=c[i-1];
		for(int i=cnt;i>=1;--i)pos[c[len[i]]--]=i;
		for(int i=cnt;i>=2;--i)
        {
			cx=pos[i];
			e.adde(link[cx],cx);
			siz[link[cx]]+=siz[cx];
			sz[link[cx]]+=sz[cx];
			clen[cx]=len[cx]-len[link[cx]];
			if(sz[cx]>sz[s[link[cx]]])s[link[cx]]=cx;
		}
		top[1]=1;dfs(1);
        return ;
    }
    inline int f(int id,int le)
    {
        while(len[link[top[id]]]>=le)id=link[top[id]];
        int l=dfn[top[id]],r=dfn[id],w=0;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(len[rk[mid]]>=le)w=mid,r=mid-1;
            else l=mid+1;
        }
        return rk[w];
    }
}sa[2];
struct C
{
	int cs,st[N],ed[N],c[N];
	unsigned long long s[N],val[N],tag[N];
	inline void init()
    {
        for(int i=1;i<=n*2;++i)c[i]=(i-1)/cl+1,ed[c[i]]=i;
		for(int i=n*2;i;--i)st[c[i]]=i;
        return ;
	}
	inline void clear()
    {
		for(int i=1;i<=n*2;++i)val[i]=s[i]=0;
		for(int i=1;i<=m;++i)tag[i]=0;
        return ;
	}
	inline void adds(int l,int r,unsigned long long v)
    {
		if(c[l]==c[r])
        {
			for(int i=l;i<=r;i++) val[i]+=v*s[i];
			return ;
		}
		for(int i=l;i<=ed[c[l]];++i) val[i]+=v*s[i];
		for(int i=c[l]+1;i<=c[r]-1;++i) tag[i]+=v;
		for(int i=st[c[r]];i<=r;++i) val[i]+=v*s[i];
        return ;
	}
	inline unsigned long long q(int x){return val[x]+tag[c[x]]*s[x];}
}fk;
struct NODE
{
	int cnt,s[N<<1],sum[N],L,R,zz;
	unsigned long long val[N<<2];
	vector<node>qq[2][N];
	inline void solve()
    {
		for(int k=0;k<=1;++k)
        {
			cx=1;
			fk.clear();
			for(int i=1;i<=tot;++i)
            {
				sum[i]=cx;
				cx+=sa[k].vec[i].size();
				for(int j=0;j<sa[k].vec[i].size();++j)fk.s[sum[i]+j]=(!k)?vr[sa[k].vec[i][j]]:vl[sa[k].vec[i][j]];
			}
			for(int i=1;i<=sa[k^1].cnt;++i)
            {
				xk=sa[k^1].rk[i],zz=sa[k^1].tag[xk];
				L=sa[k].vec[zz].size()-sa[k^1].clen[xk]+sum[zz],R=sa[k].vec[zz].size()-1+sum[zz];
				fk.adds(L,R,occ[zz]*((!k)?vl[xk]:vr[xk]));
				for(node r:qq[k][i])
                {
					for(int j=r.x;j<=r.y;++j)
                    {
						int v=sa[k].rk[j],dis=0;
						int bo=sa[k].tag[v];
						dis=sa[k].len[rt[k][bo]]-sa[k].len[v];
						val[r.id]+=r.val*fk.q(sum[bo]+sa[k].vec[bo].size()-dis-1);
					}
				}
			}
		}
        return ;
	}
	inline void work()
    {
		sort(q.begin(),q.end(),cmp);
		for(int i=0;i<(int)q.size();++i)
        {
			if(l<q[i].x)qq[0][r].push_back((node){l+1,q[i].x,++cnt,1}),l=q[i].x;
			if(r<q[i].y)qq[1][l].push_back((node){r+1,q[i].y,++cnt,1}),r=q[i].y;
			if(l>q[i].x)qq[0][r].push_back((node){q[i].x+1,l,++cnt,(unsigned long long)-1}),l=q[i].x;
			if(r>q[i].y)qq[1][l].push_back((node){q[i].y+1,r,++cnt,(unsigned long long)-1}),r=q[i].y;
			s[i]=cnt;
		}
		fk.init();
		solve();
		for(int i=1;i<=cnt;++i)val[i]+=val[i-1];
		for(int i=0;i<q.size();++i)ans[q[i].id]+=q[i].val*val[s[i]];
	}
}fxk;
int main()
{
    n=qread();
    m=qread();
    cin>>(ch+1);
    for(int i=1;i<=n;++i)wl[i]=qread();
    for(int i=1;i<=n;++i)wr[i]=qread();
    sa[0].T=sa[1].T=sa[0].cnt=sa[1].cnt=1;
    for(int i=1;i<=n;i++)sa[0].addc(ch[i]),sa[0].rg[sa[0].ed[i]=sa[0].T]=i;
	for(int i=n;i>=1;i--)sa[1].addc(ch[i]),sa[1].rg[sa[1].ed[i]=sa[1].T]=i;
	sa[0].init(),sa[1].init();
    for(int i=2;i<=sa[0].cnt;++i)
    {
        cx=sa[0].pos[i];
        L=sa[0].rg[cx]-sa[0].len[cx]+1,R=sa[0].rg[cx];
        xk=sa[1].f(sa[1].ed[L],R-L+1);
        if(sa[1].len[xk]==R-L+1)
        {
            sa[0].tag[cx]=sa[1].tag[xk]=++tot;
            rt[0][tot]=cx,rt[1][tot]=xk;
            occ[tot]=sa[0].siz[cx];
        }
    }
    for(int i=sa[0].cnt;i>=2;--i)
    {
        cx=sa[0].pos[i];
        if(!sa[0].tag[cx])for(char chr='a';chr<='z';++chr)sa[0].ch[cx][chr]&&(sa[0].tag[cx]=sa[0].tag[sa[0].ch[cx][chr]]);
    }
    for(int i=sa[1].cnt;i>=2;--i)
    {
        cx=sa[1].pos[i];
        if(!sa[1].tag[cx])for(char chr='a';chr<='z';++chr)sa[1].ch[cx][chr]&&(sa[1].tag[cx]=sa[1].tag[sa[1].ch[cx][chr]]);
    }
    for(int i=2;i<=sa[0].cnt;--i)
    {
        cx=sa[0].pos[i];
        sa[0].vec[sa[0].tag[cx]].push_back(cx);
    }
    for(int i=2;i<=sa[1].cnt;--i)
    {
        cx=sa[1].pos[i];
        sa[1].vec[sa[1].tag[cx]].push_back(cx);
    }
    for(int i=tot;i;--i)
    {
        for(int j:sa[0].vec[i])
        {
            for(int k=sa[0].e.head[j];k;k=sa[0].e.nex[k])vr[j]+=vr[sa[0].e.t[k]];
            if(sa[0].len[j]==sa[0].rg[j])vr[j]+=wr[sa[0].rg[j]];
        }
        for(int j:sa[1].vec[i])
        {
            for(int k=sa[1].e.head[j];k;k=sa[1].e.nex[k])vl[j]+=vl[sa[1].e.t[k]];
            if(sa[1].len[j]==n-sa[1].rg[j]+1)vl[j]+=wl[sa[1].rg[j]];
        }
    }
    for(int i=1,x,X,y,Y;i<=m;++i)
    {
        x=qread();
        y=qread();
        X=qread();
        Y=qread();
        cx=sa[0].f(sa[0].ed[Y],Y-X+1);
        xk=sa[1].f(sa[1].ed[x],y-x+1);
        int l1=sa[0].dfn[cx],r1=sa[0].dfn[cx]+sa[0].sz[cx]-1,l2=sa[1].dfn[xk],r2=sa[1].dfn[xk]+sa[1].sz[xk]-1;
        if(sa[0].tag[cx]==sa[1].tag[xk])
        {
			int zz=sa[0].len[rt[0][sa[1].tag[xk]]]-(sa[1].rg[xk]-sa[1].rg[rt[1][sa[1].tag[xk]]]+sa[0].rg[rt[0][sa[1].tag[xk]]]-sa[0].rg[cx]);
			if(sa[0].clen[cx]-1>=sa[1].rg[xk]-sa[1].rg[rt[1][sa[1].tag[xk]]]&&(y-x+1>zz||Y-X+1>zz))ans[i]-=occ[sa[1].tag[xk]]*vl[xk]*vr[cx];
        }
        else
        {
            Q[0][sa[0].tag[cx]].push_back((node){sa[0].len[cx]-(Y-X),r2,i,-vr[cx]});
			Q[0][sa[0].tag[cx]].push_back((node){sa[0].clen[cx],r2,i,vr[cx]});
			Q[0][sa[0].tag[cx]].push_back((node){sa[0].len[cx]-(Y-X),l2-1,i,vr[cx]});
			Q[0][sa[0].tag[cx]].push_back((node){sa[0].clen[cx],l2-1,i,-vr[cx]});
			Q[1][sa[1].tag[xk]].push_back((node){sa[1].len[xk]-(y-x),r1,i,-vl[xk]});
			Q[1][sa[1].tag[xk]].push_back((node){sa[1].clen[xk],r1,i,vl[xk]});
			Q[1][sa[1].tag[xk]].push_back((node){sa[1].len[xk]-(y-x),l1-1,i,vl[xk]});
			Q[1][sa[1].tag[xk]].push_back((node){sa[1].clen[xk],l1-1,i,-vl[xk]});
        }
        q.push_back((node){r1,r2,i,1});
		q.push_back((node){r1,l2-1,i,(unsigned long long)-1});
		q.push_back((node){l1-1,r2,i,(unsigned long long)-1});
		q.push_back((node){l1-1,l2-1,i,1});
    }
    for(int i=1;i<=tot;++i)
    {
		for(int k=0;k<=1;++k)
        {
			++bit.tim;
			sort(Q[k][i].begin(),Q[k][i].end());
			cx=Q[k][i].size()-1;
			while(cx>=0&&Q[k][i][cx].x==sa[k^1].vec[i].size())--cx;
			for(int j=0;j<sa[k^1].vec[i].size();++j)
            {
				xk=sa[k^1].vec[i][j];
				bit.adds(sa[k^1].dfn[xk],k==0?vl[xk]:vr[xk]);
				while(cx>=0&&sa[k^1].vec[i].size()-j-1==Q[k][i][cx].x)
                {
					node S=Q[k][i][cx];
					ans[S.id]+=occ[i]*S.val*bit.ask(S.y);
					--cx;
				}
			}
		}
	}
    for(int i=1;i<=n*2;++i)c[i]=(i-1)/cl+1;
    fxk.work();
    for(int i=1;i<=m;++i)printf("%llu\n",ans[i]);
    return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 8ms
memory: 51808kb

input:

500 500
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 1st lines differ - expected: '15720454042420499810', found: '0'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Time Limit Exceeded

Test #22:

score: 0
Time Limit Exceeded

input:

100000 100000
zbbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaabab...

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #2:

0%

Subtask #7:

score: 0
Skipped

Dependency #3:

0%