luogu P2574 XOR的艺术 (线段树)

算是比较简单的线段树.

当区间修改时.\(1 xor 1 = 0,0 xor 1 = 1\)所以就是区间元素个数减去以前的\(1\)的个数就是现在\(1\)的个数.

#include <iostream>

#include <cstdio>

#define lson now << 1

#define rson now << 1 | 1

const int maxN = 2e5 + 7;

struct Node {

	int l,r,Xor,sum;

}tree[maxN << 2];

void updata(int now) {

	tree[now].sum = tree[lson].sum + tree[rson].sum;

	return;

}

void build(int l,int r,int now) {

	tree[now].l = l;tree[now].r = r;

	if(l == r) {

		int a;

		scanf("%1d",&a);

		tree[now].sum = a ? 1 : 0;

		return;

	}

	int mid = (l + r) >> 1;

	build(l,mid,lson);

	build(mid + 1,r,rson);

	updata(now);

	return;

}

void work(int now) {

	tree[now].sum = tree[now].r - tree[now].l + 1 - tree[now].sum;

	tree[now].Xor ^= 1;

	return;

}

void pushdown(int now) {

	if(!tree[now].Xor) return;

	work(lson);

	work(rson);

	tree[now].Xor = 0;

	return;

}

void modify(int l,int r,int now) {

	if(tree[now].l >= l && tree[now].r <= r)  {

		work(now);

		return;

	}

	int mid = (tree[now].l + tree[now].r) >> 1;

	pushdown(now);

	if(mid >= l) modify(l,r,lson);

	if(mid < r) modify(l,r,rson);

	updata(now);

	return;

}

int query(int l,int r,int now) {

	if(tree[now].l >= l && tree[now].r <= r)

		return tree[now].sum;

	int mid = (tree[now].l + tree[now].r) >> 1,sum = 0;

	pushdown(now);

	if(mid >= l) sum += query(l,r,lson);

	if(mid < r) sum += query(l,r,rson);

	return sum;

}

int main() {

	int n,m;

	scanf("%d%d",&n,&m);

	build(1,n,1);

	int type,l,r;

	while(m --) {

		scanf("%d%d%d",&type,&l,&r);

		if(type) printf("%d\n", query(l,r,1));

		else modify(l,r,1);

	}

	return 0;

}

巴特西

luogu P2574 XOR的艺术 (线段树)

luogu P2574 XOR的艺术 (线段树)

最新文章

热门文章