P2574 XOR的艺术 题解

CSDN同步

原题链接

简要题意:

给定一个长度为 \(n\) 的 \(01\) 序列 \(a\),\(q\) 次操作:

  • 对 \([l,r]\) 区间进行异或操作(即 \(0 \gets 1, 1 \gets 0\))
  • 询问 \([l,r]\) 区间中 \(1\) 的个数。

\(n,q \leq 2 \times 10^5\).

算法一 分块

显然 \(\mathcal{O}(nq)\) 的暴力是不可能通过这道题目的。

考虑如何分块。

令块长为 \(S\),对于 \(\lfloor \frac{n}{S} \rfloor\) 个块,初始化其中 \(0\) 和 \(1\) 的个数。

下面对于每个修改操作,对整块则直接交换 \(0,1\) 的参数,不完整块则暴力修改

对于询问,整块直接返回 \(1\) 的个数,不玩整块则直接暴力统计

时间复杂度:\(\mathcal{O}(Sq + \lfloor \frac{n}{S} \rfloor q)\).

显然想让这个复杂度最小,令 \(S = \sqrt{n}\) 是最佳选择,复杂度为 \(\mathcal{O}(n \sqrt{n})\).

实际上暴力也是一种优雅的分块,它只是 \(S=1\) 而已。

算法二 线段树

假设这个题开到 \(n,q \leq 2 \times 10^6\),显然分块就无能为力解决了。

考虑如何用线段树解决?

还是用代码讲吧。线段树板子相信大家都会,那讲起来会非常方便。

初始化部分

#define L (x<<1)
#define R (x<<1)+1

这是一个声明,\(L\) 即 \(x\) 的左儿子节点,\(R\) 即 \(x\) 的右儿子节点!

struct T {
	int l,r,z,o,tag;
} T[N<<2];

线段树常规套路,\([l,r]\) 区间中有 \(z\) 个 \(0\),\(o\) 个 \(1\). \(\text{tag}\) 表示 \([l,r]\) 区间被修改的次数(懒标记)。

inline void build_tree(int x,int l,int r) {
	T[x].tag=0; T[x].l=l; T[x].r=r;
	if(l==r) {
		if(s[l-1]=='1') T[x].o=1; else T[x].z=1;
		return;
	} int mid=(l+r)>>1;
	build_tree(L,l,mid);
	build_tree(R,mid+1,r);
	update(x);
}	

建树过程也很套路。注释都有,大致思路就是,元区间直接搞,其余区间用它的左右儿子拼起来。\(\text{update}\) 是如何更新的呢?看这一段:

inline void update(int x) {
	T[x].z=T[L].z+T[R].z;
	T[x].o=T[L].o+T[R].o;
} 

直接暴力统计,应该没啥问题吧!

build_tree 复杂度为 \(\mathcal{O}(n)\).很好理解吧!

初始化结束之后,我们只需要考虑三个函数的写法:

  • \(\text{pushdown}\)
  • \(\text{change}\)(可能你会写成 \(\text{modify}\))
  • \(\text{query}\)(可能你会写成 \(\text{ask}\))

修改

下面重讲修改操作。

线段树套路修改:完全包含则暴力修改,打标记;否则下传标记,并分两个区间去修改。修改完成后用 \(\text{update}\) 再更新一遍。

inline void change(int x,int l,int r) {
	if(l<=T[x].l && T[x].r<=r) {
		swap(T[x].z,T[x].o); T[x].tag^=1; //暴力修改,交换 0,1 个数
		return;
	} pushdown(x); int mid=(T[x].l+T[x].r)>>1;
	if(l<=mid) change(L,l,r);
	if(r>mid) change(R,l,r); //往两边区间走
	update(x); //再更新
}

你会说了:为什么是 T[x].tag^=1 而不是 T[x].tag++ 呢?

很明显,对 同一个区间进行两次异或操作 等同于 不操作。所以 \(k\) 次操作等同于 \(k \& 1\) 次操作。自然抵消一定操作可以进行常数优化。(你想,\(k\) 次的 \(\text{swap}\) 两个数肯定会化成 \(0\) 和 \(1\) 次啊)

那么,\(\text{pushdown}\) 怎么写呢?

inline void pushdown(int x) {
	int p=T[x].tag; if(!p) return;
	swap(T[L].o,T[L].z); T[L].tag^=1; //左边
	swap(T[R].o,T[R].z); T[R].tag^=1; //右边
	T[x].tag=0; //清空标记
}

修改单次的复杂度是 \(\mathcal{O}(\log n)\) 的,因为最多把树高走一遍,而树高是 \(\log\) 的。

询问

询问就是套路了吧!

包含区间直接返回,否则下传标记,分两个区间合并答案即可。(有时候合并答案并不是运算那么简单,就像 最大子段和 的合并)当然这题的合并只需要 \(+\) 就行。

inline int query(int x,int l,int r) {
	if(l<=T[x].l && T[x].r<=r) return T[x].o;
	pushdown(x); int mid=(T[x].l+T[x].r)>>1,ans=0;
	if(l<=mid) ans+=query(L,l,r);
	if(r>mid) ans+=query(R,l,r);
	return ans;
}

全是套路,忽略不计吧。

单次询问的复杂度也是 \(\mathcal{O}(\log n)\),同样最多把树高跑一遍。

代码

\(480 \text{ms} , 10.82 \text{MB}\),性能还不错,最慢的点 \(189 \text{ms}\).

最后给一个代码吧:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+1;
#define L (x<<1)
#define R (x<<1)+1

inline int read(){char ch=getchar(); int f=1; while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0; while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}

inline void write(int x) {
	if(x<0) {putchar('-');write(-x);return;}
	if(x<10) {putchar(char(x%10+'0'));return;}
	write(x/10);putchar(char(x%10+'0'));
}
int n,m;
char s[N];
struct T {
	int l,r,z,o,tag;
} T[N<<2];
inline void update(int x) {
	T[x].z=T[L].z+T[R].z;
	T[x].o=T[L].o+T[R].o;
} 
inline void pushdown(int x) {
	int p=T[x].tag; if(!p) return;
	swap(T[L].o,T[L].z); T[L].tag^=1;
	swap(T[R].o,T[R].z); T[R].tag^=1;
	T[x].tag=0;
}
inline void build_tree(int x,int l,int r) {
	T[x].tag=0; T[x].l=l; T[x].r=r;
	if(l==r) {
		if(s[l-1]=='1') T[x].o=1; else T[x].z=1;
		return;
	} int mid=(l+r)>>1;
	build_tree(L,l,mid);
	build_tree(R,mid+1,r);
	update(x);
}	
inline void change(int x,int l,int r) {
	if(l<=T[x].l && T[x].r<=r) {
		swap(T[x].z,T[x].o); T[x].tag^=1;
		return;
	} pushdown(x); int mid=(T[x].l+T[x].r)>>1;
	if(l<=mid) change(L,l,r);
	if(r>mid) change(R,l,r);
	update(x); 
}
inline int query(int x,int l,int r) {
	if(l<=T[x].l && T[x].r<=r) return T[x].o;
	pushdown(x); int mid=(T[x].l+T[x].r)>>1,ans=0;
	if(l<=mid) ans+=query(L,l,r);
	if(r>mid) ans+=query(R,l,r);
	return ans;
}

int main() {
	n=read(),m=read(); scanf("%s",s);
	build_tree(1,1,n); while(m--) {
		int op=read(),l=read(),r=read();
		if(op==1) printf("%d\n",query(1,l,r));
		else change(1,l,r);
	}
	return 0;
}


上一篇:[CF741D]Arpa's letter-marked tree and Mehrdad's Dokhtar-kosh paths


下一篇:java 简单xor加密