当前位置：首页 > article >正文

洛谷 P2574 XOR的艺术

article 2025/1/30 12:06:18

洛谷题目传送门

题目描述

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

拥有一个伤害串，是一个长度为 n 的只含字符 0 和字符 1 的字符串。规定这个字符串的首字符是第一个字符，即下标从 1 开始。
给定一个范围 [l, r]，伤害为伤害串的这个范围内中字符 1 的个数。
会修改伤害串中的数值，修改的方法是把 [l, r] 中所有原来的字符 0 变成 1，将 1 变成 0。

AKN 想知道一些时刻的伤害，请你帮助他求出这个伤害。

输入格式

输入的第一行有两个用空格隔开的整数，分别表示伤害串的长度 n，和操作的个数 m。

输入第二行是一个长度为 n 的字符串 S，代表伤害串。

第 33 到第 (m+2) 行，每行有三个用空格隔开的整数 op,l,r。代表第 i 次操作的方式和区间，规则是：

若 op=0，则表示将伤害串的 [l, r] 区间内的 0 变成 1，1 变成 0。
若 op=1，则表示询问伤害串的 [l, r] 区间内有多少个字符 1。

输出格式

对于每次询问，输出一行一个整数，代表区间内 1 的个数。

输入输出样例

输入

输出

3
6
1

说明/提示

样例输入输出解释

原伤害串为 1011101001。

对于第一次操作，改变 [2, 4]的字符，伤害串变为 1100101001。

对于第二次操作，查询 [1, 5] 内 1 的个数，共有 3个。

对于第三次操作，改变 [3, 7]的字符，伤害串变为 1111010001。

对于第四次操作，查询 [1, 10] 内 1 的个数，共有 6 个。

对于第五次操作，改变 [1, 4] 的字符，伤害串变为 0000010001。

对于第六次操作，查询 [2, 6] 内 1 的个数，共有 1 个。

数据范围与约定

对于 10% 的数据，保证 $n,m\leq 10$ 。

另有 30% 的数据，保证 $n,m\leq 2\times 10^{3}$ 。

对于 100% 的数据，保证 $2\leq n,m\leq 2\times 10^{5}$ ， $0\leq op\leq 1$ ， $1\leq l\leq r\leq n$ ，S 中只含字符 0 和字符 1。

思路

首先，查询区间 [ l , r ] 内一共有多少个 1 即为求区间 [ l , r ] 的区间和

由于要区间修改，我们~~根据题目标签~~很自然就想到了线段树，我们只需要在模板的基础上修改一下就行了

如果将 u 对应的区间 [ l , r ] 中的 1 变为 0，0 变为 1，区间和 sum 的变化如何？

显然，变化后的 sum1=l-r+1-sum，因为 0 和 1 互换了，所以原来 0 的数量即为现在 1 的数量

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+5;
ll n,m,a[N];
struct S{
	ll l,r,data,lzy;// l 为左边界，r 为右边界，lzy 为懒标记，data 为当前节点的值(区间和，区间最值)
};
class edge_tree {//线段树
private:
	S tree[N*4];
public:
	void pushup_sum(ll u){tree[u].data=tree[u<<1].data+tree[u<<1|1].data;}//更新 tree[u].data
	void add_sum(ll u){//将 u 对应区间中的 0 和 1 互换
		tree[u].lzy^=1;
		tree[u].data=((tree[u].r-tree[u].l+1)-tree[u].data);
	}
	void pushdown(ll u){//懒标记下传
		if(!tree[u].lzy)return;//如果未打上懒标记，跳过
		add_sum(u<<1);add_sum(u<<1|1);//分别传到左、右子树
		tree[u].lzy=0;//已经下传了就清空标记
	}
	void build(ll u,ll l,ll r){//建立线段树
		tree[u]=(S){l,r,0};//节点 u 所对区间为 [l,r]
		if(l==r){tree[u].data=a[l];tree[u].lzy=0;return;}//如果 u 为叶子节点，tree[u].data 就是 a[l]，而且叶子节点无左右子树，跳过建左右子树
		ll mid=(l+r)/2;
		build(u<<1,l,mid);build(u<<1|1,mid+1,r);//分别建立左右子树
		pushup_sum(u);//更新 tree[u].data
	}
	void chang(ll u,ll x,ll y){//将区间 [x,y] 中的 0 和 1 互换
		if(tree[u].l>y||tree[u].r<x)return;//如果当前区间与 [x,y] 无交集，跳过
		if(tree[u].l>=x&&tree[u].r<=y){add_sum(u);return;}//如果 [x,y] 完全包含当前区间，当前区间直接加上 v
		pushdown(u);//标记下传(更新子树)
		chang(u<<1,x,y);chang(u<<1|1,x,y);//分别修改左右子树
		pushup_sum(u);//更新 tree[u].data
	}
	ll get_sum(ll u,ll x,ll y){//求区间 [x,y] 的和
		ll l=tree[u].l,r=tree[u].r;
		if(y<l||x>r)return 0;//如果当前区间与 [x,y] 无交集，跳过
		if(x<=l&&r<=y)return tree[u].data;//如果 [x,y] 完全包含当前区间，直接返回当前区间的和
		pushdown(u);//标记下传(同上)
		return get_sum(u<<1,x,y)+get_sum(u<<1|1,x,y);//分别遍历左右子树
	}
}etree;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	char ch;
	for(ll i=1;i<=n;i++){cin>>ch;a[i]=ch-'0';}//将字符串转换为数字
	etree.build(1,1,n);
	ll op,x,y;
	for(ll i=1;i<=m;i++){
		cin>>op;
		if(op==0){cin>>x>>y;etree.chang(1,x,y);}
		else {cin>>x>>y;cout<<etree.get_sum(1,x,y)<<'\n';}
	}
	return 0;
}

查看全文

http://www.kler.cn/a/522810.html