QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#561348#7839. 虹DaiRuiChen0070 3ms30068kbC++173.0kb2024-09-12 21:58:412024-09-12 21:58:42

Judging History

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

  • [2024-09-12 21:58:42]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:30068kb
  • [2024-09-12 21:58:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=8e4+5,B=282,X=19901991,Y=20242024;
int n,q,z[MAXN],bel[MAXN],lp[MAXN],rp[MAXN];
vector <int> G[MAXN];
int fa[MAXN],dfn[MAXN],dcnt,st[MAXN][18],dl[MAXN][18],dr[MAXN][18];
int bit(int x) { return 1<<x; }
int cmp(int x,int y) { return dfn[x]<dfn[y]?x:y; }
int qdl(int l,int r) {
	int k=__lg(r-l+1);
	return min(dl[l][k],dl[r-bit(k)+1][k]);
}
int qdr(int l,int r) {
	int k=__lg(r-l+1);
	return max(dr[l][k],dr[r-bit(k)+1][k]);
}
int lca(int l,int r) {
	int k=__lg(r-l+1);
	return cmp(st[l][k],st[r-bit(k)+1][k]);
}
void dfs0(int u,int fz) {
	fa[u]=fz,dl[u][0]=dr[u][0]=dfn[u]=++dcnt,st[dcnt][0]=fz;
	for(int v:G[u]) if(v^fz) dfs0(v,u);
}
int op[MAXN],ql[MAXN],qr[MAXN];
bitset <MAXN> F[MAXN],S;
vector <int> wl[MAXN],wr[MAXN],wx[MAXN],LCA[MAXN];
void add(bitset<MAXN>&s,int u) { for(;u&&!s[u];u=fa[u]) s.set(u); }
void dfs1(int u) {
	S.set(u);
	for(int i:LCA[u]) F[i]^=S;
	for(int v:G[u]) if(v^fa[u]) dfs1(v);
	S.reset(u);
}
int pr[MAXN],tot,g[MAXN];
bool isc[MAXN];
void dfs2(int o,int x) {
	if(o>tot) {
		for(int i:wx[x]) F[i]^=S;
		return ;
	}
	int p=pr[o],pw=1;
	dfs2(o+1,x);
	while(x<=n) {
		if(1ll*x*p>n) break;
		x*=p,pw*=p;
		for(int i=pw;i<=n;i+=pw) S[i]=z[g[i]*=p];
		dfs2(o+1,x);
	}
	for(int i=p;i<=n;i+=p) {
		while(g[i]%p==0) g[i]/=p;
		S[i]=z[g[i]];
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin>>n>>q;
	for(int i=1;i<=n;++i) cin>>z[i],z[i]&=1;
	for(int i=1;(i-1)*B+1<=n;++i) {
		lp[i]=(i-1)*B+1,rp[i]=min(i*B,n);
		fill(bel+lp[i],bel+rp[i]+1,i);
	}
	for(int i=1,u,v;i<n;++i) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
	dfs0(1,0);
	for(int k=1;k<18;++k) for(int i=1;i+bit(k)-1<=n;++i) {
		st[i][k]=cmp(st[i][k-1],st[i+bit(k-1)][k-1]);
		dl[i][k]=min(dl[i][k-1],dl[i+bit(k-1)][k-1]);
		dr[i][k]=max(dr[i][k-1],dr[i+bit(k-1)][k-1]);
	}
	for(int i=1,x;i<=q;++i) {
		cin>>op[i]>>ql[i]>>qr[i];
		if(op[i]==1) {
			LCA[lca(qdl(ql[i],qr[i])+1,qdr(ql[i],qr[i]))].push_back(i);
			if(bel[ql[i]]==bel[qr[i]]) for(int u=ql[i];u<=qr[i];++u) add(F[i],u);
			else wl[bel[ql[i]]].push_back(i),wr[bel[ql[i]]+1].push_back(i);
		} else cin>>x,wx[x].push_back(i);
	}
	for(int o=1;o<=bel[n];++o) {
		sort(wl[o].begin(),wl[o].end(),[&](int x,int y){ return ql[x]>ql[y]; });
		sort(wr[o].begin(),wr[o].end(),[&](int x,int y){ return qr[x]<qr[y]; });
		S.reset();
		for(int i=lp[o],j=0,s=wr[o].size();j<s&&i<=n;++i) {
			add(S,i);
			while(j<s&&qr[wr[o][j]]==i) F[wr[o][j++]]|=S;
		}
		S.reset();
		for(int i=rp[o],j=0,s=wl[o].size();j<s&&i>=lp[o];--i) {
			add(S,i);
			while(j<s&&ql[wl[o][j]]==i) F[wl[o][j++]]|=S;
		}
	}
	S.reset(),dfs1(1);
	for(int i=1;i<=q;++i) F[i]^=F[i-1];
	for(int i=2;i<=n;++i) if(!isc[i]) {
		pr[++tot]=i;
		for(int j=2*i;j<=n;j+=i) isc[j]=true;
	}
	S.reset();
	for(int i=1;i<=n;++i) S[i]=z[g[i]=1];
	dfs2(1,1);
	for(int i=1;i<=q;++i) if(op[i]==2) {
		int l=ql[i],r=qr[i];
		F[i]>>=l,F[i]<<=(MAXN-(r-l+1));
		int s=F[i].count();
		cout<<(1ll*s*(X-1)+r-l+1)%Y<<"\n";
	}
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 30068kb

input:

998 1000
955556485 952505211 899166521 258704448 894183248 636280051 62949347 983956660 113872828 588367167 208142006 665025449 944228063 284736189 169202015 56096447 404419923 30158095 111191865 717455344 790159420 391379127 208279658 426780799 886604643 940903663 618716147 773652834 385881251 1593...

output:

17521890
5641174
16841705
9201073
7001063
11621851
11281891
13621482
10221161
1560472
19782496
3080467
17902259
17402322
440957
14821686
12101396
10081761
14682021
6841052
5481071
760883
16181858
3981054
20082242
10721137
8340896
700265
3460983
11441570
3760552
6321069
11581353
4460869
17042086
1888...

result:

wrong answer 1st lines differ - expected: '16521790', found: '17521890'

Subtask #2:

score: 0
Time Limit Exceeded

Test #4:

score: 0
Time Limit Exceeded

input:

65531 65535
968854923 932574892 192297572 866236747 654755663 148562561 273214896 947434573 938626677 992982166 219888853 229840279 676071061 383387319 372883953 729287797 601010887 31942080 990584163 823724544 181337075 918252129 896876911 768539961 357780649 890577681 819641335 320266037 55445939 ...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%