超绝超可爱线段树
查看原帖
超绝超可爱线段树
726139
残阳如血楼主2023/10/18 13:42

你说得对,线段树很闪,但是【小粉兔】太难写了!

#include <iostream>
const int MAXN = 2e5 + 10;

int n, m, a[MAXN], w[4 * MAXN], lzy[4 * MAXN];

void pushup(int u) {
	w[u] = w[u * 2] + w[u * 2 + 1];
}

void maketag(int u, int l, int r) {
	w[u] = r - l + 1 - w[u], lzy[u] ^= 1;
}

void pushdown(int u, int l, int r) {
	int mid = (l + r) / 2;
	maketag(u * 2, l, mid);
	maketag(u * 2 + 1, mid + 1, r);
	lzy[u] ^= 1;
}

void build(int u, int l, int r) {
	if (l == r) {
		w[u] = a[l];
		return ;
	}
	int mid = (l + r) / 2;
	build(u * 2, l, mid);
	build(u * 2 + 1, mid + 1, r);
	pushup(u);
}

int queryNode(int u, int l, int r, int p) {
	if (l == r) return w[u];
	int mid = (l + r) / 2;
	pushdown(u, l, r);
	if (mid >= p) return queryNode(u * 2, l, mid, p);
	else return queryNode(u * 2 + 1, mid + 1, r, p);
}

void updateNode(int u, int l, int r, int p) {
	if (l == r) {
		w[u] ^= 1;
		return ;
	}
	int mid = (l + r) / 2;
	pushdown(u, l, r);
	if (p <= mid) updateNode(u * 2, l, mid, p);
	else updateNode(u * 2 + 1, mid + 1, r, p);
	pushup(u);
}

int query(int u, int l, int r, int tarl, int tarr) {
	if (tarl > r || tarr < l) return 0;
  if (tarl >= l && tarr <= r) return w[u];
	int mid = (l + r) / 2;
	pushdown(u, l, r);
	return query(u * 2, l, mid, tarl, tarr) + query(u * 2 + 1, mid + 1, r, tarl, tarr);
}

void update(int u, int l, int r, int tarl, int tarr) {
	if (tarl > r || tarr < l) return ;
  if (tarl >= l && tarr <= r)  {
		maketag(u, l, r);
		return ;
	}
	int mid = (l + r) / 2;
	pushdown(u, l, r);
	update(u * 2, l, mid, tarl, tarr);
	update(u * 2 + 1, mid + 1, r, tarl, tarr);
}

int main() {
	int n, m; std::cin >> n >> m;
	for (int a, b, c; m; --m) {
		std::cin >> c >> a >> b;
		if (c == 0) update(1, 1, n, a, b);
		else std::cout << query(1, 1, n, a, b) << '\n';
	}
	return 0;
}

求助 qwq

2023/10/18 13:42
加载中...