洛谷P2574 XOR的艺术

时间:2023-12-29 08:28:38

题目描述

\(AKN\)觉得第一题太水了,不屑于写第一题,所以他又玩起了新的游戏。在游戏中,他发现,这个游戏的伤害计算有一个规律,规律如下

1、 拥有一个伤害串为长度为\(n\)的\(01\)串。

2、 给定一个范围\([l,r]\),伤害为伤害串的这个范围内中\(1\)的个数

3、 会被随机修改伤害串中的数值,修改的方法是把\([l,r]\)中的所有数\(xor\)上\(1\)

\(AKN\)想知道一些时刻的伤害,请你帮助他求出这个伤害

输入输出格式

输入格式:

第一行两个数\(n,m\),表示长度为\(n\)的\(01\)串,有\(m\)个时刻

第二行一个长度为\(n\)的\(01\)串,为初始伤害串

第三行开始\(m\)行,每行三个数\(p,l,r\)

若\(p\)为\(0\),则表示当前时刻改变\([l,r]\)的伤害串,改变规则如上

若\(p\)为\(1\),则表示当前时刻\(AKN\)想知道\([l,r]\)的伤害

输出格式:

对于每次询问伤害,输出一个数值伤害,每次询问输出一行

输入输出样例

输入样例#1:

10 6
1011101001
0 2 4
1 1 5
0 3 7
1 1 10
0 1 4
1 2 6

输出样例#1:

3
6
1

说明

样例解释:

\(1011101001\)

\(1100101001\)

询问\([1,5]\)输出\(3\)

\(1111010001\)

询问\([1,10]\)输出\(6\)

\(0000010001\)

询问\([2,6]\)输出\(1\)

数据范围:

\(10\%\)数据\(2≤n,m≤10\)

另有\(30\%\)数据\(2≤n,m≤2000\)

\(100\%\)数据\(2≤n,m≤2*10^5\)

思路:这是一道跟洛谷\(P2574\)思路类似的一道题目,唯一不同的就是这道题需要建树,因为初始值不都是\(0\),然后对于此题,区间修改操作就是区间异或运算,区间查询就是查询区间中\(1\)的个数,然后用线段树维护区间中\(1\)的个数即可。

代码:

#include<cstdio>
#include<cctype>
#define maxn 200007
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
int n,m,sum[maxn<<2],lazy[maxn<<2];
inline int qread() {
char c=getchar();int num=0,f=1;
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) num=num*10+c-'0';
return num*f;
}
inline void pushup(int rt) {
sum[rt]=sum[ls]+sum[rs];
}
void build(int rt, int l, int r) {
if(l==r) {
scanf("%1d",&sum[rt]);
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(rt);
}
inline void pushdown(int rt, int len) {
if(lazy[rt]) {
lazy[ls]^=1;
lazy[rs]^=1;
sum[ls]=(len-(len>>1))-sum[ls];
sum[rs]=(len>>1)-sum[rs];
lazy[rt]=0;
}
}
void modify(int rt, int l, int r, int L, int R) {
if(L>r||R<l) return;
if(L<=l&&r<=R) {
lazy[rt]^=1;
sum[rt]=r-l+1-sum[rt];
return;
}
pushdown(rt,r-l+1);
int mid=(l+r)>>1;
modify(ls,l,mid,L,R),modify(rs,mid+1,r,L,R);
pushup(rt);
}
int csum(int rt, int l, int r, int L, int R) {
if(L>r||R<l) return 0;
if(L<=l&&r<=R) return sum[rt];
pushdown(rt,r-l+1);
int mid=(l+r)>>1;
return csum(ls,l,mid,L,R)+csum(rs,mid+1,r,L,R);
}
int main() {
n=qread(),m=qread();
build(1,1,n);
for(int i=1,k,l,r;i<=m;++i) {
k=qread(),l=qread(),r=qread();
if(!k) modify(1,1,n,l,r);
else printf("%d\n",csum(1,1,n,l,r));
}
return 0;
}