你说得对,线段树很闪,但是【小粉兔】太难写了!
#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