自动搬运

查看原文

来自洛谷，原作者为

	龙行龘龘 这个家伙不懒，但还是什么都没留下

搬运于2025-08-24 22:08:30，当前版本为作者最后更新于2019-09-06 22:05:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

水题为什么没人做???

问题显然可以转化成带修地查询区间内前缀异或和为给定数的数量

根据题面来看,把所有按钮都取反跟原来是一样，也就是2^4=16种状态

区间修改为某个数的影响最多只有1次（两两抵消）

线段树上打打标记就可以了...

顺便献上我的blog:https://www.luogu.org/blog/Root-std-admin/

只给伪代码了嗷:

void build(int &p,int l,int r) {
	if (p==0) p=++num,t[p].l=t[p].r=t[p].sum=t[p].y=0,t[p].a=-1;
	t[p].c[N[0]]=((r-l)>>1)+(!(l&1)||!(r&1));
	t[p].c[N[o[0]]]=((r-l)>>1)+((l&1)||(r&1));
	t[p].sum=((((r-l)>>1)+((l&1)||(r&1)))&1)*o[0];
	if (l==r) return;
	int mid=l+r>>1;
	build(t[p].l,l,mid);
	build(t[p].r,mid+1,r);
}
void pd(int p,int l,int r) {
	if (t[p].a!=-1) {
		if (t[p].l) t[t[p].l].a=t[p].a,t[t[p].l].V=t[p].V,t[t[p].l].Q=t[p].Q,t[t[p].l].y=0;
		if (t[p].r) t[t[p].r].a=t[p].a,t[t[p].r].V=t[p].V,t[t[p].r].Q=t[p].Q,t[t[p].r].y=0;
		memset(t[p].c,0,sizeof(t[p].c));
		t[p].c[N[t[p].V]]=((r-l)>>1)+(!(l-t[p].Q&1)||!(r-t[p].Q&1));
		t[p].c[N[t[p].a^t[p].V]]=((r-l)>>1)+((l-t[p].Q&1)||(r-t[p].Q&1));
		t[p].sum=((((r-l)>>1)+((l-t[p].Q&1)||(r-t[p].Q&1)))&1)*t[p].a^((r-l+1&1)*t[p].V);
		t[p].a=-1;
	}
}
void up(int p,int l,int r) {
	int mid=l+r>>1;
	pd(t[p].l,l,mid);
	pd(t[p].r,mid+1,r);
	t[p].sum=t[t[p].l].sum^t[t[p].r].sum^(((mid-l+1)&1)*t[t[p].l].y)^(((r-mid)&1)*t[t[p].r].y);
	for (int i=0; i<16; i++) t[p].c[i]=t[t[p].l].c[N[s[i]^t[t[p].l].y]]+t[t[p].r].c[N[s[i]^t[t[p].r].y]];
}
void cg(int p,int l,int r,int po,int v) {
	if (po<=l) t[p].y^=v;
	else {
		pd(p,l,r);
		int mid=l+r>>1;
		cg(t[p].r,mid+1,r,po,v);
		if (mid>=po) cg(t[p].l,l,mid,po,v);
		up(p,l,r);
	}
}
int ask(int p,int l,int r,int po) {
	if (t[p].a!=-1) return (t[p].a*(po-t[p].Q&1))^t[p].V^t[p].y;
	if (l==r) return t[p].sum^t[p].y;
	int mid=l+r>>1;
	if (po<=mid) return ask(t[p].l,l,mid,po)^t[p].y;
	else return ask(t[p].r,mid+1,r,po)^t[p].y;
}
int que(int p,int l,int r,int L,int R,int v) {
	pd(p,l,r);
	v^=t[p].y;
	if (L==l&&R==r) return t[p].c[N[v]];
	int mid=l+r>>1;
	if (R<=mid) return que(t[p].l,l,mid,L,R,v);
	else if (L>mid) return que(t[p].r,mid+1,r,L,R,v);
	else
		return que(t[p].l,l,mid,L,mid,v)+que(t[p].r,mid+1,r,mid+1,R,v);
}
void ca(int p,int l,int r,int L,int R,int v,int V,int Q) {
	if (L==l&&R==r) {
		t[p].a=v;
		t[p].V=V;
		t[p].y=0;
		t[p].Q=Q;
		t[p].c[N[V]]=((r-l)>>1)+(!(l-Q&1)||!(r-Q&1));
		t[p].c[N[v^V]]=((r-l)>>1)+((l-Q&1)||(r-Q&1));
		t[p].sum=(((((r-l)>>1)+((l-Q&1)||(r-Q&1)))&1)*v)^((r-l+1&1)*V);
	} else {
		pd(p,l,r);
		V^=t[p].y;
		int mid=l+r>>1;
		if (R<=mid) ca(t[p].l,l,mid,L,R,v,V,Q);
		else if (L>mid) ca(t[p].r,mid+1,r,L,R,v,V,Q);
		else
			ca(t[p].l,l,mid,L,mid,v,V,Q),ca(t[p].r,mid+1,r,mid+1,R,v,V,Q);
		up(p,l,r);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	register int i,j;
	rx=read();
	ry=read();
	n=0;
	for (i=0; i<rx; i++)
		for (j=0; j<ry; j++) o[i]^=1<<(i*ry+j),o[j+rx]^=1<<(i*ry+j),q^=read()<<(i*ry+j);
	n=read();
	m=read();
	s[bo=num=0]=0;
	for(; bo<=num;) {
		for (i=0; i<rx+ry; i++) {
			for (j=0; j<=num; j++)
				if (s[j]==(s[bo]^o[i])) break;
			if (j>num) s[++num]=s[bo]^o[i];
			to[bo][i]=j;
		}
		bo++;
	}
	for (i=0; i<64; i++) N[i]=-1;
	for (i=0; i<=num; i++) N[s[i]]=i;
	num=0;
	build(ro,1,n);
	while (m--) {
		bo=read();
		if (bo==0) bo=read(),cg(ro,1,n,bo,o[read()-1]^ask(ro,1,n,bo)^(bo==1?0:ask(ro,1,n,bo-1)));
		else if (bo==1) if (bo=read(),x=read(),N[q]==-1) puts("0");
			else printf("%d\n",que(ro,1,n,bo,x,q));
		else if (rx=read(),ry=read(),x=o[read()-1],cg(ro,1,n,ry+1,ask(ro,1,n,ry)^(((ry-rx+1)&1)*x)),ca(ro,1,n,rx,ry,x,0,rx-1),rx-1) cg(ro,1,n,rx,ask(ro,1,n,rx-1));
	}
	return 0;
}

哦对,MN看数据范围,好像是1e6吧...

真心感谢大家观看,谢谢!!!