QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#79941#5014. 复读程度NATURAL60 1505ms600808kbC++148.6kb2023-02-21 13:25:002023-02-21 13:25:01

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:25:01]
  • 评测
  • 测评结果:0
  • 用时:1505ms
  • 内存:600808kb
  • [2023-02-21 13:25:00]
  • 提交

answer

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 200010

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<typename sa> bool chkmax(sa &x,sa y){return x<y?x=y,1:0;}
template<typename sa> bool chkmin(sa &x,sa y){return x>y?x=y,1:0;}

ull readint(){
	ull x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

struct node{
	int x,y,id; ull w;
	node(int x=0,int y=0,int id=0,ull w=0):x(x),y(y),id(id),w(w){}
	bool operator<(const node c)const{return x==c.x?y<c.y:x<c.x;}
};

const int B=400;
int n,m,q,bcnt;
int occ[200005],rt[2][200005];
ull ans[100005],wl[100005],wr[100005],vl[200005],vr[200005];
char s[100005];
vector<node> qry;

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 ;
    }
};

namespace bit{
	int tim,tag[N];
	unsigned long long val[N];
    inline int lowbit(int x){return x&-x;}
	inline void add(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;
	}
}

struct sam
{
    int cx,xk,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];
vector<node> subqry[2][200005];
namespace blo{
	int m;
	int lf[1005],rg[1005],bl[200005];
	ull a[200005],val[200005],tag[1005];
	void init(){
		for(int i=1;i<=n*2;++i)bl[i]=(i-1)/B+1,rg[bl[i]]=i;
		for(int i=n*2;i;--i)lf[bl[i]]=i;
	}
	void clear(){
		for(int i=1;i<=n+n;i++) val[i]=a[i]=0;
		for(int i=1;i<=m;i++) tag[i]=0;
	}
	void add(int l,int r,ull c){
		int lb=bl[l],rb=bl[r];
		if(lb==rb){
			for(int i=l;i<=r;i++) val[i]+=c*a[i];
			return;
		}
		for(int i=l;i<=rg[lb];i++) val[i]+=c*a[i];
		for(int i=lf[rb];i<=r;i++) val[i]+=c*a[i];
		for(int i=lb+1;i<=rb-1;i++) tag[i]+=c;
	}
	ull ask(int x){
		return val[x]+tag[bl[x]]*a[x];
	}
}

namespace sub1{
	int cnt;
	int plq[400005],st[200005];
	ull val[800005];
	vector<node> qry2[2][200005];
	void solve(){
		for(int l=0;l<2;l++){
			int now=1;
			blo::clear();
			for(int i=1;i<=bcnt;i++){
				st[i]=now;
				now+=sa[l].vec[i].size();
				for(int j=0;j<sa[l].vec[i].size();j++) blo::a[st[i]+j]=(!l)?vr[sa[l].vec[i][j]]:vl[sa[l].vec[i][j]];
			}
			for(int i=1;i<=sa[l^1].cnt;i++){
				int u=sa[l^1].rk[i];
				int bel=sa[l^1].tag[u];
				int L=sa[l].vec[bel].size()-sa[l^1].clen[u],R=sa[l].vec[bel].size()-1;
				L+=st[bel],R+=st[bel];
				blo::add(L,R,occ[bel]*(l==0?vl[u]:vr[u]));
				for(auto r:qry2[l][i]){
					for(int j=r.x;j<=r.y;j++){
						int v=sa[l].rk[j],dis=0;
						int bo=sa[l].tag[v];
						dis=sa[l].len[rt[l][bo]]-sa[l].len[v];
						val[r.id]+=r.w*blo::ask(st[bo]+sa[l].vec[bo].size()-dis-1);
					}
				}
			}
		}
	}
	void work(){
		sort(qry.begin(),qry.end(),[&](node x,node y){
			if((x.x-1)/B==(y.x-1)/B) return (x.x-1)/B%2==0?x.y<y.y:x.y>y.y;
			return (x.x-1)/B<(y.x-1)/B;
		});
		int nx=0,ny=0;
		for(int i=0;i<qry.size();i++){
			node r=qry[i];
			if(nx<r.x) qry2[0][ny].pb(node(nx+1,r.x,++cnt,1)),nx=r.x;
			if(ny<r.y) qry2[1][nx].pb(node(ny+1,r.y,++cnt,1)),ny=r.y;
			if(nx>r.x) qry2[0][ny].pb(node(r.x+1,nx,++cnt,-1)),nx=r.x;
			if(ny>r.y) qry2[1][nx].pb(node(r.y+1,ny,++cnt,-1)),ny=r.y;
			plq[i]=cnt;
		}
		blo::init();
		solve();
		for(int i=1;i<=cnt;i++) val[i]+=val[i-1];
		for(int i=0;i<qry.size();i++) ans[qry[i].id]+=qry[i].w*val[plq[i]];
	}
}

int main(){
	n=readint(); q=readint();
	scanf("%s",s+1);
	for(int i=1;i<=n;i++) wl[i]=readint();
	for(int i=1;i<=n;i++) wr[i]=readint();
	sa[0].cnt=sa[0].T=sa[1].cnt=sa[1].T=1;
	for(int i=1;i<=n;i++) sa[0].addc(s[i]-'a'),sa[0].rg[sa[0].ed[i]=sa[0].T]=i;
	for(int i=n;i>=1;i--) sa[1].addc(s[i]-'a'),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++){
		int u=sa[0].pos[i];
		int L=sa[0].rg[u]-sa[0].len[u]+1,R=sa[0].rg[u];
		int id=sa[1].f(sa[1].ed[L],R-L+1);
		if(sa[1].len[id]==R-L+1){
			sa[0].tag[u]=sa[1].tag[id]=++bcnt;
			rt[0][bcnt]=u,rt[1][bcnt]=id;
			occ[bcnt]=sa[0].siz[u];
		}
	}
	for(int i=0;i<2;i++){
		for(int j=sa[i].cnt;j>=2;j--){
			int u=sa[i].pos[j];
			if(sa[i].tag[u]) continue;
			for(int k=0;k<26;k++) if(sa[i].ch[u][k]) sa[i].tag[u]=sa[i].tag[sa[i].ch[u][k]];
		}
	}
	for(int i=0;i<2;i++){
		for(int j=2;j<=sa[i].cnt;j++){
			int u=sa[i].pos[j];
			sa[i].vec[sa[i].tag[u]].pb(u);
		}
	}
	for(int i=bcnt;i>=1;i--){
		for(auto r:sa[0].vec[i]){
			for(int v=sa[0].e.head[r];v;v=sa[0].e.nex[v]) vr[r]+=vr[sa[0].e.t[v]];
			if(sa[0].len[r]==sa[0].rg[r]) vr[r]+=wr[sa[0].rg[r]];
		}
		for(auto r:sa[1].vec[i]){
			for(int v=sa[1].e.head[r];v;v=sa[1].e.nex[v]) vl[r]+=vl[sa[1].e.t[v]];
			if(sa[1].len[r]==n-sa[1].rg[r]+1) vl[r]+=wl[sa[1].rg[r]];
		}
	}
	int x1,y1,x2,y2;
	for(int i=1;i<=q;i++){
		x1=readint(); y1=readint(); x2=readint(); y2=readint();
		int p1=sa[1].f(sa[1].ed[x1],y1-x1+1);
		int p0=sa[0].f(sa[0].ed[y2],y2-x2+1);
		int l1=sa[0].dfn[p0],r1=sa[0].dfn[p0]+sa[0].sz[p0]-1;
		int l2=sa[1].dfn[p1],r2=sa[1].dfn[p1]+sa[1].sz[p1]-1;
		if(sa[1].tag[p1]==sa[0].tag[p0]){
			int len=sa[0].len[rt[0][sa[1].tag[p1]]]-(sa[1].rg[p1]-sa[1].rg[rt[1][sa[1].tag[p1]]]+sa[0].rg[rt[0][sa[1].tag[p1]]]-sa[0].rg[p0]);
			if(sa[0].clen[p0]-1>=sa[1].rg[p1]-sa[1].rg[rt[1][sa[1].tag[p1]]]&&(y1-x1+1>len||y2-x2+1>len)) ans[i]-=occ[sa[1].tag[p1]]*vl[p1]*vr[p0];
		}
		else{
			subqry[0][sa[0].tag[p0]].pb(node(sa[0].len[p0]-(y2-x2),r2,i,-vr[p0]));
			subqry[0][sa[0].tag[p0]].pb(node(sa[0].clen[p0],r2,i,vr[p0]));
			subqry[0][sa[0].tag[p0]].pb(node(sa[0].len[p0]-(y2-x2),l2-1,i,vr[p0]));
			subqry[0][sa[0].tag[p0]].pb(node(sa[0].clen[p0],l2-1,i,-vr[p0]));
			subqry[1][sa[1].tag[p1]].pb(node(sa[1].len[p1]-(y1-x1),r1,i,-vl[p1]));
			subqry[1][sa[1].tag[p1]].pb(node(sa[1].clen[p1],r1,i,vl[p1]));
			subqry[1][sa[1].tag[p1]].pb(node(sa[1].len[p1]-(y1-x1),l1-1,i,vl[p1]));
			subqry[1][sa[1].tag[p1]].pb(node(sa[1].clen[p1],l1-1,i,-vl[p1]));
		}
		qry.pb(node(r1,r2,i,1));
		qry.pb(node(r1,l2-1,i,-1));
		qry.pb(node(l1-1,r2,i,-1));
		qry.pb(node(l1-1,l2-1,i,1));
	}
	for(int i=1;i<=bcnt;i++){
			for(int k=0;k<2;k++){
				bit::tim++;
				sort(subqry[k][i].begin(),subqry[k][i].end());
				int now=(int)subqry[k][i].size()-1;
				while(now>=0&&subqry[k][i][now].x==sa[k^1].vec[i].size()) now--;
				for(int j=0;j<sa[k^1].vec[i].size();j++){
					int r=sa[k^1].vec[i][j];
					bit::add(sa[k^1].dfn[r],k==0?vl[r]:vr[r]);
					while(now>=0&&sa[k^1].vec[i].size()-j-1==subqry[k][i][now].x){
						node nd=subqry[k][i][now];
						ans[nd.id]+=occ[i]*nd.w*bit::ask(nd.y);
						now--;
					}
				}
			}
		}
	sub1::work();
	for(int i=1;i<=q;i++) printf("%llu\n",ans[i]);
	puts("-");
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 11ms
memory: 51860kb

input:

500 500
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

15720454042420499810
4058077030882532408
14651762045124606089
4030024243931986061
18033423360813892607
9470601111824364484
3883374861354698625
16650831689368240202
8339028189650687576
2683289915379600554
13133811958066776394
14181220923901262251
18173739360450512256
13142314545999179754
148925491596...

result:

wrong output format Extra information in the output file

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #22:

score: 0
Wrong Answer
time: 1505ms
memory: 600808kb

input:

100000 100000
zbbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaabab...

output:

16102224067619618967
2409962914769200003
427496158535942638
17668679206267169316
9612725428377010375
16283030984784184667
14966758574838045581
8108029333542434517
5821899279772898061
7354415533246368927
15016230232022193055
9072126619623269970
5490256818353051548
432088324301719512
13681741566473101...

result:

wrong output format Extra information in the output file

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #2:

0%

Subtask #7:

score: 0
Skipped

Dependency #3:

0%