QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#473825 | #6427. Just Another Game of Stones | Linx | WA | 2880ms | 34400kb | C++23 | 3.8kb | 2024-07-12 14:25:43 | 2024-07-12 14:25:43 |
Judging History
answer
#include <bits/stdc++.h>
#define log(x) (31^__builtin_clz(x))
using namespace std;
const int maxn=2e5+5;
int n,q,a[maxn],op,l,r,x;
inline int read() {
int 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<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int maxm=500+5;
int bel[maxn],st[maxm],ed[maxm];
int Max[maxm];
bool vis[maxm];
int loc[maxm];
vector<int>qwq[maxm],Xor[maxm],sum[30][maxm];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin>>n>>q;
for(int i=1;i<=n;++i) cin>>a[i];
int block=sqrt(n)+3;
for(int i=1;i<=(n-1)/block+1;++i) {
vis[i]=1;
st[i]=(i-1)*block+1;
ed[i]=min(i*block,n);
for(int j=st[i];j<=ed[i];++j) {
bel[j]=i;
qwq[i].push_back(a[j]);
Xor[i].push_back(0);
for(int k=0;k<=29;++k) sum[k][i].push_back(0);
}
sort(qwq[i].begin(),qwq[i].end());
for(int j=0;j<qwq[i].size();++j) {
if(j==0) {
Xor[i][j]=qwq[i][j];
for(int k=0;k<=29;++k) sum[k][i][j]=((qwq[i][j]>>k)&1);
}
else {
Xor[i][j]=(Xor[i][j-1]^qwq[i][j]);
for(int k=0;k<=29;++k) sum[k][i][j]=((qwq[i][j]>>k)&1)+sum[k][i][j-1];
}
}
}
while(q--) {
cin>>op>>l>>r>>x;
if(op==1) {
int s=bel[l]+1,t=bel[r]-1;
for(int i=s;i<=t;++i) Max[i]=max(Max[i],x),vis[i]=1;
vis[s-1]=vis[t+1]=1;
for(int i=st[s-1];i<l;++i) {
a[i]=max(a[i],Max[s-1]);
//if(l<=i&&i<=r) a[i]=max(a[i],x);
qwq[s-1][i-st[s-1]]=a[i];
}
for(int i=l;i<=ed[s-1];++i) {
a[i]=max({a[i],Max[s-1],x});
//if(l<=i&&i<=r) a[i]=max(a[i],x);
qwq[s-1][i-st[s-1]]=a[i];
}
Max[s-1]=0;
sort(qwq[s-1].begin(),qwq[s-1].end());
for(int i=0;i<qwq[s-1].size();++i) {
if(i==0) {
Xor[s-1][i]=qwq[s-1][i];
for(int k=0;k<=29;++k) sum[k][s-1][i]=((qwq[s-1][i]>>k)&1);
}
else {
Xor[s-1][i]=(Xor[s-1][i-1]^qwq[s-1][i]);
for(int k=0;k<=29;++k) sum[k][s-1][i]=((qwq[s-1][i]>>k)&1)+sum[k][s-1][i-1];
}
}
if(bel[l]!=bel[r]) {
for(int i=st[t+1];i<=r;++i) {
a[i]=max({a[i],Max[t+1],x});
//if(l<=i&&i<=r) a[i]=max(a[i],x);
qwq[t+1][i-st[t+1]]=a[i];
}
for(int i=r+1;i<=ed[t+1];++i) {
a[i]=max({a[i],Max[t+1],x});
//if(l<=i&&i<=r) a[i]=max(a[i],x);
qwq[t+1][i-st[t+1]]=a[i];
}
Max[t+1]=0;
sort(qwq[t+1].begin(),qwq[t+1].end());
for(int i=0;i<qwq[t+1].size();++i) {
if(i==0) {
Xor[t+1][i]=qwq[t+1][i];
for(int k=0;k<=29;++k) sum[k][t+1][i]=((qwq[t+1][i]>>k)&1);
}
else {
Xor[t+1][i]=(Xor[t+1][i-1]^qwq[t+1][i]);
for(int k=0;k<=29;++k) sum[k][t+1][i]=((qwq[t+1][i]>>k)&1)+sum[k][t+1][i-1];
}
}
}
}
else {
int s=bel[l]+1,t=bel[r]-1;
int tmp=0;
for(int i=s;i<=t;++i) {
int p;
if(vis[i])p=upper_bound(qwq[i].begin(),qwq[i].end(),Max[i])-qwq[i].begin();
else p=loc[i];
loc[i]=p;vis[i]=0;
int len=qwq[i].size();
tmp^=(Xor[i][len-1]^Xor[i][p-1]);
if(p&1) tmp^=Max[i];
}
for(int i=l;i<=min(r,ed[s-1]);++i) tmp^=max(a[i],Max[s-1]);
if(bel[l]!=bel[r]) {
for(int i=st[t+1];i<=r;++i) tmp^=max(a[i],Max[t+1]);
}
tmp^=x;
if(tmp==0) cout<<"0\n";
else {
int js=-1;
int ans=0;
if((tmp^x)<x) ans++;
while(tmp) js++,tmp>>=1;
for(int i=l;i<=min(r,ed[s-1]);++i) if((max(a[i],Max[s-1])&(1<<js))) ans++;
if(bel[l]!=bel[r]) {
for(int i=st[t+1];i<=r;++i) if((max(a[i],Max[t+1])&(1<<js))) ans++;
}
for(int i=s;i<=t;++i) {
int p;
if(vis[i])p=upper_bound(qwq[i].begin(),qwq[i].end(),Max[i])-qwq[i].begin();
else p=loc[i];
loc[i]=p;vis[i]=0;
int len=qwq[i].size();
if((Max[i]&(1<<js))) ans+=p;
ans+=sum[js][i][len-1]-sum[js][i][p-1];
}
cout<<ans<<"\n";
}
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3816kb
input:
5 4 1 2 1 4 1 2 1 3 1 1 2 4 3 2 2 4 4 2 1 4 4
output:
1 0 3
result:
ok 3 number(s): "1 0 3"
Test #2:
score: -100
Wrong Answer
time: 2880ms
memory: 34400kb
input:
200000 200000 962352030 173642520 1008864183 74920228 684681800 500911321 1001441054 257633652 185843534 59168654 317689197 731348417 123888883 708119712 340055368 876566011 980078202 969174443 814012870 715639041 596932238 173757742 314504576 1045746913 740811577 570187156 999816627 12441059 122507...
output:
38889 57353 46659 19709 34625 127805 1211 755 16087 25267 14051 12263 33399 5223 41869 21117 97277 16733 64611 737 32715 25031 148859 17395 76263 56261 19825 93349 44653 22291 31645 9833 34641 95623 79651 39321 153 6067 6445 25369 9041 35785 39783 111237 151543 54289 121169 165785 101803 101519 1527...
result:
wrong answer 5th numbers differ - expected: '34617', found: '34625'