P2574 XOR的艺术
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;
}