QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#474086 | #6427. Just Another Game of Stones | Kaiser_Kell | RE | 0ms | 3764kb | C++23 | 2.8kb | 2024-07-12 16:02:10 | 2024-07-12 16:02:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
const int Inf=0x3f3f3f3f;
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;
}
int n,q,a[maxn],op,l,r,x;
struct Node{
int l,r,sum,Min,se,cnt;
int lazy;
int js[30];
}tree[maxn<<2];
void pushup(int rt) {
tree[rt].Min=min(tree[rt<<1].Min,tree[rt<<1|1].Min);
if(tree[rt<<1].Min==tree[rt<<1|1].Min) {
tree[rt].se=min(tree[rt<<1].se,tree[rt<<1|1].se);
tree[rt].cnt=tree[rt<<1].cnt+tree[rt<<1|1].cnt;
}
else if(tree[rt<<1].Min<tree[rt<<1|1].Min) {
tree[rt].se=min(tree[rt<<1].se,tree[rt<<1|1].Min);
tree[rt].cnt=tree[rt<<1].cnt;
}
else {
tree[rt].se=min(tree[rt<<1].Min,tree[rt<<1|1].se);
tree[rt].cnt=tree[rt<<1|1].cnt;
}
tree[rt].sum=(tree[rt<<1].sum^tree[rt<<1|1].sum);
for(int k=0;k<=29;++k) tree[rt].js[k]=tree[rt<<1].js[k]+tree[rt<<1|1].js[k];
}
void build(int rt,int l,int r) {
tree[rt].l=l,tree[rt].r=r;
if(l==r) {
tree[rt].sum=a[l];
tree[rt].Min=a[l];
tree[rt].cnt=1;
tree[rt].se=Inf;
for(int k=0;k<=29;++k) tree[rt].js[k]=((a[l]>>k)&1);
return;
}
int mid=l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
pushup(rt);
}
void update(int rt,int x) {
if(tree[rt].cnt&1) tree[rt].sum^=(tree[rt].Min^x);
for(int k=0;k<=29;++k) {
if((tree[rt].Min>>k)&1) tree[rt].js[k]-=tree[rt].cnt;
if((x>>k)&1) tree[rt].js[k]+=tree[rt].cnt;
}
tree[rt].Min=x;
tree[rt].lazy=max(tree[rt].lazy,x);
}
void pushdown(int rt) {
if(tree[rt].lazy) {
if(tree[rt<<1].Min<=tree[rt].lazy&&tree[rt].lazy<tree[rt<<1].se) update(rt<<1,tree[rt].lazy);
if(tree[rt<<1|1].Min<=tree[rt].lazy&&tree[rt].lazy<tree[rt<<1|1].se) update(rt<<1|1,tree[rt].lazy);
tree[rt].lazy=0;
}
}
void update_max(int rt,int l,int r,int L,int R,int x) {
if(L>r||R<l||x<=tree[rt].Min) return;
if(L<=l&&R>=r&&x<tree[rt].se) {
update(rt,x);
return;
}
pushdown(rt);
if(l!=r) {
int mid=l+r>>1;
update_max(rt<<1,l,mid,L,R,x);
update_max(rt<<1|1,mid+1,r,L,R,x);
pushup(rt);
}
}
int Xor,sum[30];
void query(int rt,int l,int r,int L,int R) {
if(R<l||L>r) return;
if(L<=l&&R>=r) {
for(int k=0;k<=29;++k) sum[k]+=tree[rt].js[k];
Xor^=tree[rt].sum;
return;
}
pushdown(rt);
int mid=l+r>>1;
query(rt<<1,l,mid,L,R);
query(rt<<1|1,mid+1,r,L,R);
return;
}
int main() {
n=read(),q=read();
for(int i=1;i<=n;++i) a[i]=read();
build(1,1,n);
while(q--) {
op=read(),l=read(),r=read(),x=read();
if(op==1) update_max(1,1,n,l,r,x);
else {
Xor=0;
for(int k=0;k<=29;++k) sum[k]=0;
query(1,1,n,l,r);
Xor^=x;
int ans=0;
if((Xor^x)<x) ans++;
int p=-1;
while(Xor) p++,Xor>>=1;
printf("%d\n",ans+sum[p]);
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3764kb
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
Runtime Error
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...