洛谷 P2574 XOR的艺术/CF242E XOR on Segment 题解

1.XOR的艺术

题意

给定一个长度为$n$的、只含有数字$0,1$的字符串和两种操作。

对于每种操作，给定$op,l,r$：

$op=0$表示将字符串的$[l,r]$区间内的$0$变成$1$，$1$变成$0$。

$op=1$表示询问字符串的$[l,r]$区间内有多少个字符$1$。

思路

一段区间中非$0$即$1$，那么该区间中$1$的个数，其实就是区间求和，考虑使用线段树解决这个问题。

对于$op=0$这个取反操作，设区间左右端点分别为$l,r$，原来的$1$个数为$sum$；取反一次，原来$1$的位置有$sum$处变成$0$，而原来为$0$的位置有$(r-l+1)-sum$处变成$1$，相当于现在$1$的个数$su{m}^{\prime }=(r-l+1)-sum$

知道了怎么更新区间了就好办了，但是为了节省时间就要引入懒标记$tag$

可以令其表示区间要被处理的次数，在下次修改或查询时当次数为奇数时才$pushdown$下放（因为翻转两次就相当于没反转）

也可以直接让$tag=0$或$1$，来表示需不需要执行翻转操作，每次更新就异或一次$1$

线段树就只需要维护区间和$sum$即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls u<<1
#define rs u<<1|1
const ll N=2e5+9;
ll n,m,a[N];
char c[N];
struct SegT
{struct node{ll sum,tag;}T[N<<4];void pushup(ll u){T[u].sum=T[ls].sum+T[rs].sum;}void pushdown(ll u,ll l,ll r){if(T[u].tag){ll mid=(l+r)>>1;T[ls].sum=(mid-l+1)-T[ls].sum;T[rs].sum=(r-mid)-T[rs].sum;}T[ls].tag^=T[u].tag;T[rs].tag^=T[u].tag;T[u].tag=0;}void build(ll u,ll l,ll r){if(l==r){T[u].sum=a[l];return;}ll mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(u);}void modify(ll u,ll l,ll r,ll ql,ll qr){if(qr<l||r<ql)return;if(ql<=l&&r<=qr){T[u].sum=(r-l+1)-T[u].sum;T[u].tag^=1;return;}pushdown(u,l,r);ll mid=(l+r)>>1;if(ql<=mid)modify(ls,l,mid,ql,qr);if(qr>mid)modify(rs,mid+1,r,ql,qr);pushup(u);}ll query(ll u,ll l,ll r,ll ql,ll qr){if(qr<l||r<ql)return 0;if(ql<=l&&r<=qr)return T[u].sum;pushdown(u,l,r);ll mid=(l+r)>>1,ret=0;if(ql<=mid)ret+=query(ls,l,mid,ql,qr);if(qr>mid)ret+=query(rs,mid+1,r,ql,qr);return ret;}
}A;
int main()
{scanf("%lld%lld%s",&n,&m,c+1);for(int i=1;i<=n;i++)a[i]=c[i]-'0';A.build(1,1,n);while(m--){ll op,l,r;scanf("%lld%lld%lld",&op,&l,&r);if(op==0)A.modify(1,1,n,l,r);if(op==1)printf("%lld\n",A.query(1,1,n,l,r));}return 0;
}

2.XOR on Segment

题意

给定$n$个数的序列$a$。$m$次操作，操作有两种：

对于每种操作，给定$op,l,r$：

$op=1$表示要求区间$[l,r]$内所有数的和

$op=2$时，给定$x$，并将区间$[l,r]$所有数异或上$x$

$1\le n\le 10^5,1\le m\le 5\times 10^4,1\le x,a_i\le 10^6$

思路

对比上一题，本题将$0$和$1$的序列推广到$[1,10^6]$，大了不少。

但能否和上一题产生关联呢？

当然是可以的！可以考虑用$0,1$表示序列中每个数的二进制，因为$1\le a_i\le 10^6$，所以二进制最多有$\lceil {\log }_{2}10^6\rceil =20$位。可以开$20$棵线段树来维护$20$个进制位，做法和上一题大差不差了。

修改的时候如果$x$与当前第$i$位的“基底”$2^i$作且操作，即$xand{2}^i=0$时，那就无需对这一位更新，因为异或$0$相当于不用异或。

最后预处理$2$的幂，然后逐位相加就能得到查询的答案。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls u<<1
#define rs u<<1|1
const int N=1e5+9,M=20;
int n,m,a[N];
int _2[M];
void init()
{_2[0]=1;for(int i=1;i<M;i++)_2[i]=_2[i-1]*2;
}
struct SegT
{struct node{ll sum;int tag;}T[N<<2];void pushup(int u){T[u].sum=T[ls].sum+T[rs].sum;}void pushdown(int u,int l,int r){if(T[u].tag){int mid=(l+r)>>1;T[ls].sum=(mid-l+1)-T[ls].sum;T[rs].sum=(r-mid)-T[rs].sum;T[ls].tag^=T[u].tag;T[rs].tag^=T[u].tag;T[u].tag=0;}}void build(int u,int l,int r,int ws){if(l==r){T[u].sum=(ll)(a[l]&_2[ws]?1:0);return;}int mid=(l+r)>>1;build(ls,l,mid,ws);build(rs,mid+1,r,ws);pushup(u);}void modify(int u,int l,int r,int ql,int qr){if(qr<l||r<ql)return;if(ql<=l&&r<=qr){T[u].sum=(ll)(r-l+1)-T[u].sum;T[u].tag^=1;return;}pushdown(u,l,r);int mid=(l+r)>>1;if(ql<=mid)modify(ls,l,mid,ql,qr);if(qr>mid)modify(rs,mid+1,r,ql,qr);pushup(u);}ll query(int u,int l,int r,int ql,int qr){if(qr<l||r<ql)return 0;if(ql<=l&&r<=qr)return T[u].sum;pushdown(u,l,r);int mid=(l+r)>>1;ll ret=0;if(ql<=mid)ret+=(ll)query(ls,l,mid,ql,qr);if(qr>mid)ret+=(ll)query(rs,mid+1,r,ql,qr);return ret;}
}A[M];
int main()
{init();scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=0;i<M;i++)A[i].build(1,1,n,i);scanf("%d",&m);while(m--){int op,l,r;scanf("%d%d%d",&op,&l,&r);if(op==1){ll ans=0;for(int i=0;i<M;i++)ans+=1ll*_2[i]*A[i].query(1,1,n,l,r);printf("%lld\n",ans);}else {int x;scanf("%d",&x);for(int i=0;i<M;i++)if(x&_2[i])A[i].modify(1,1,n,l,r);}}return 0;
}