QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#561348 | #7839. 虹 | DaiRuiChen007 | 0 | 3ms | 30068kb | C++17 | 3.0kb | 2024-09-12 21:58:41 | 2024-09-12 21:58:42 |
Judging History
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%