QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#474086#6427. Just Another Game of StonesKaiser_KellRE 0ms3764kbC++232.8kb2024-07-12 16:02:102024-07-12 16:02:10

Judging History

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

  • [2024-07-12 16:02:10]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3764kb
  • [2024-07-12 16:02:10]
  • 提交

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...

output:


result: