自动搬运

查看原文

来自洛谷，原作者为

	Sshenyyyu **

搬运于2025-08-24 21:39:14，当前版本为作者最后更新于2018-09-16 19:44:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

XOR的艺术

题目前两个字母吼吼吼

一道简单模板题

思路

与平常的线段树不同的是，这次不是区间加法，区间乘法等基础操作，而是神奇的取反，让我不由自主的想到题目XOR（嘻嘻嘻QAQ） 那我们怎么办呢？？只有01哦，不错！！

请看神奇的栗子一枚

区间中取反，我们只需要求的是和，伤害值是1的个数，不就是和嘛！！哈哈哈！！！

看，10101，有3个1，取反过后，01010，就变成2个1啦！！就是5-3=2

在看，00110，有2个1，取反过后，11001，就变成2个1啦！！就是5-2=3

所以呢，区间和，每次在下传懒惰标记的时候呢，就变成区间长度减去自身的值就阔以啦！！！

棒棒哒！！

上代码吧！！！蒟蒻代码，不喜勿喷

至于一些头文件定义什么的省略啦，空间不够，嘻嘻嘻！！！

struct node
{
	int left;//区间左端点
	int right;//右端点
	int w;//初值
	int v;//标记
}tree[Maxn*2];

void Build_Tree(int index,int l,int r)//神奇建树，连函数名都是那么的直接。。。
{
	tree[index].left=l;
	tree[index].right=r;
	if(l==r) {
		tree[index].w=a[l];
		return;
	}
	int mid=(l+r)/2;
	Build_Tree(index*2,l,mid);
	Build_Tree(index*2+1,mid+1,r);
	tree[index].w=tree[index*2].w+tree[index*2+1].w;
}//建树很简单，不说啦！！

void Spread(int index)//下传懒惰标记
{
	if(tree[index].v) {
		tree[index*2].w=tree[index*2].right-tree[index*2].left+1-tree[index*2].w;//如上所说修改
		tree[index*2+1].w=tree[index*2+1].right-tree[index*2+1].left+1-tree[index*2+1].w;
		tree[index*2].v^=1;//标记很简单，就直接取反好啦！！
		tree[index*2+1].v^=1;
		tree[index].v=0;//别忘记清空！！
	}
}

int Query(int index,int l,int r)//自认为好理解的查询。。。
{
	if(tree[index].left>=l&&tree[index].right<=r) return tree[index].w;//如果完全包含，返回区间
	int mid=(tree[index].left+tree[index].right)/2;
	int ans=0;
	Spread(index);//下传标记
	if(l<=mid) ans+=Query(index*2,l,r);//继续向下
	if(r>mid) ans+=Query(index*2+1,l,r);
	return ans;
}

void Change(int index,int l,int r)//修改区间很简单，不说啦！！！
{
	if(tree[index].left>=l&&tree[index].right<=r) {
		tree[index].w=tree[index].right-tree[index].left+1-tree[index].w;
		tree[index].v^=1;
		return;
	}
	int mid=(tree[index].left+tree[index].right)/2;
	Spread(index);
	if(l<=mid) Change(index*2,l,r);
	if(r>mid) Change(index*2+1,l,r);
	tree[index].w=tree[index*2].w+tree[index*2+1].w;
}

int main()
{
	cin>>n>>m;
	for(int i=1; i<=n; i++)
		scanf("%1d",&a[i]);
	Build_Tree(1,1,n);
	for(int i=1; i<=m; i++) {
		cin>>z;
		if(z==0) {
			cin>>x>>y;
			Change(1,x,y);	
		}
		else {
			cin>>x>>y;
			cout<<Query(1,x,y)<<endl;	
		}
	}
	return 0;
}

没啦，蒟蒻望大家多多支持！！！！