QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#79930#5014. 复读程度NATURAL60 1031ms168716kbC++147.9kb2023-02-21 12:57:192023-02-21 12:57:21

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 12:57:21]
  • 评测
  • 测评结果:0
  • 用时:1031ms
  • 内存:168716kb
  • [2023-02-21 12:57:19]
  • 提交

answer

// xtqqwq
#include<bits/stdc++.h>

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

using namespace std;

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

template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
template<typename T> bool chkmin(T &x,T 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=900;
int n,m,q,bcnt;
int occ[200005],rt[2][200005],bl[200005],lf[1005],rg[1005];
ull ans[100005],wl[100005],wr[100005],vl[200005],vr[200005];
char s[100005];
vector<int> vec[2][200005];
vector<node> qry;

namespace bit{
	int timer;
	int mark[200005];
	ull val[200005];
	void add(int x,ull c){
		for(;x<=n+n;x+=(x&(-x))){
			if(mark[x]!=timer) mark[x]=timer,val[x]=0;
			val[x]+=c;
		}
	}
	ull ask(int x){
		ull ret=0;
		for(;x;x-=(x&(-x))) ret+=mark[x]==timer?val[x]:0;
		return ret;
	}
}

struct sam{
	int lst,cnt,ncnt;
	int ch[200005][26],fa[200005],len[200005],siz[200005],tmp[200005],A[200005],rg[200005],tag[200005],ed[100005],sz[200005],son[200005],dfn[200005],rnk[200005],top[200005],num[200005];
	vector<int> adj[200005];
	void ins(int c){
		int p=lst,np=++cnt; lst=np,len[np]=len[p]+1,siz[np]=1;
		for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
		if(!p) return (void)(fa[np]=1);
		int q=ch[p][c];
		if(len[q]==len[p]+1) return (void)(fa[np]=q);
		int nq=++cnt;
		len[nq]=len[p]+1,rg[nq]=rg[q];
		memcpy(ch[nq],ch[q],sizeof(ch[nq]));
		fa[nq]=fa[q],fa[q]=fa[np]=nq;
		for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
	}
	void dfs(int u){
		dfn[u]=++ncnt,rnk[ncnt]=u;
		if(son[u]) top[son[u]]=top[u],dfs(son[u]);
		for(auto v:adj[u]){
			if(v==son[u]) continue;
			top[v]=v;
			dfs(v);
		}
	}
	void init(){
		for(int i=1;i<=cnt;i++) tmp[len[i]]++;
		for(int i=1;i<=n;i++) tmp[i]+=tmp[i-1];
		for(int i=cnt;i>=1;i--) A[tmp[len[i]]--]=i;
		for(int i=1;i<=cnt;i++) sz[i]=1;
		for(int i=cnt;i>=2;i--){
			int u=A[i];
			adj[fa[u]].pb(u);
			siz[fa[u]]+=siz[u];
			sz[fa[u]]+=sz[u];
			num[u]=len[u]-len[fa[u]];
			if(sz[u]>sz[son[fa[u]]]) son[fa[u]]=u;
		}
		top[1]=1; dfs(1);
	}
	int find(int x,int d){
		while(len[fa[top[x]]]>=d) x=fa[top[x]]; 
		int L=dfn[top[x]],R=dfn[x],res=0;
		while(L<=R){
			int mid=(L+R)/2;
			if(len[rnk[mid]]>=d) res=mid,R=mid-1;
			else L=mid+1;
		}
		return rnk[res];
	}
}T[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+=vec[l][i].size();
				for(int j=0;j<vec[l][i].size();j++) blo::a[st[i]+j]=(!l)?vr[vec[l][i][j]]:vl[vec[l][i][j]];
			}
			for(int i=1;i<=T[l^1].cnt;i++){
				int u=T[l^1].rnk[i];
				int bel=T[l^1].tag[u];
				int L=vec[l][bel].size()-T[l^1].num[u],R=vec[l][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=T[l].rnk[j],dis=0;
						int bo=T[l].tag[v];
						dis=T[l].len[rt[l][bo]]-T[l].len[v];
						val[r.id]+=r.w*blo::ask(st[bo]+vec[l][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();
	T[0].cnt=T[0].lst=T[1].cnt=T[1].lst=1;
	for(int i=1;i<=n;i++) T[0].ins(s[i]-'a'),T[0].rg[T[0].ed[i]=T[0].lst]=i;
	for(int i=n;i>=1;i--) T[1].ins(s[i]-'a'),T[1].rg[T[1].ed[i]=T[1].lst]=i;
	T[0].init();
	T[1].init();
	for(int i=2;i<=T[0].cnt;i++){
		int u=T[0].A[i];
		int L=T[0].rg[u]-T[0].len[u]+1,R=T[0].rg[u];
		int id=T[1].find(T[1].ed[L],R-L+1);
		if(T[1].len[id]==R-L+1){
			T[0].tag[u]=T[1].tag[id]=++bcnt;
			rt[0][bcnt]=u,rt[1][bcnt]=id;
			occ[bcnt]=T[0].siz[u];
		}
	}
	for(int i=0;i<2;i++){
		for(int j=T[i].cnt;j>=2;j--){
			int u=T[i].A[j];
			if(T[i].tag[u]) continue;
			for(int k=0;k<26;k++) if(T[i].ch[u][k]) T[i].tag[u]=T[i].tag[T[i].ch[u][k]];
		}
	}
	for(int i=0;i<2;i++){
		for(int j=2;j<=T[i].cnt;j++){
			int u=T[i].A[j];
			vec[i][T[i].tag[u]].pb(u);
		}
	}
	for(int i=bcnt;i>=1;i--){
		for(auto r:vec[0][i]){
			for(auto v:T[0].adj[r]) vr[r]+=vr[v];
			if(T[0].len[r]==T[0].rg[r]) vr[r]+=wr[T[0].rg[r]];
		}
		for(auto r:vec[1][i]){
			for(auto v:T[1].adj[r]) vl[r]+=vl[v];
			if(T[1].len[r]==n-T[1].rg[r]+1) vl[r]+=wl[T[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=T[1].find(T[1].ed[x1],y1-x1+1);
		int p0=T[0].find(T[0].ed[y2],y2-x2+1);
		int l1=T[0].dfn[p0],r1=T[0].dfn[p0]+T[0].sz[p0]-1;
		int l2=T[1].dfn[p1],r2=T[1].dfn[p1]+T[1].sz[p1]-1;
		if(T[1].tag[p1]==T[0].tag[p0]){
			int len=T[0].len[rt[0][T[1].tag[p1]]]-(T[1].rg[p1]-T[1].rg[rt[1][T[1].tag[p1]]]+T[0].rg[rt[0][T[1].tag[p1]]]-T[0].rg[p0]);
			if(T[0].num[p0]-1>=T[1].rg[p1]-T[1].rg[rt[1][T[1].tag[p1]]]&&(y1-x1+1>len||y2-x2+1>len)) ans[i]-=occ[T[1].tag[p1]]*vl[p1]*vr[p0];
		}
		else{
			subqry[0][T[0].tag[p0]].pb(node(T[0].len[p0]-(y2-x2),r2,i,-vr[p0]));
			subqry[0][T[0].tag[p0]].pb(node(T[0].num[p0],r2,i,vr[p0]));
			subqry[0][T[0].tag[p0]].pb(node(T[0].len[p0]-(y2-x2),l2-1,i,vr[p0]));
			subqry[0][T[0].tag[p0]].pb(node(T[0].num[p0],l2-1,i,-vr[p0]));
			subqry[1][T[1].tag[p1]].pb(node(T[1].len[p1]-(y1-x1),r1,i,-vl[p1]));
			subqry[1][T[1].tag[p1]].pb(node(T[1].num[p1],r1,i,vl[p1]));
			subqry[1][T[1].tag[p1]].pb(node(T[1].len[p1]-(y1-x1),l1-1,i,vl[p1]));
			subqry[1][T[1].tag[p1]].pb(node(T[1].num[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::timer++;
				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==vec[k^1][i].size()) now--;
				for(int j=0;j<vec[k^1][i].size();j++){
					int r=vec[k^1][i][j];
					bit::add(T[k^1].dfn[r],k==0?vl[r]:vr[r]);
					while(now>=0&&vec[k^1][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: 17ms
memory: 42024kb

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: 1031ms
memory: 168716kb

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%