C++(g++ 7.5.0) 解法, 执行用时: 74ms, 内存消耗: 4696K, 提交时间: 2023-03-21 08:25:22

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <functional>
using namespace std;
#define F cout<<"bug\n";
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 1e9 + 9;

const double pi = acos(-1.0);
const double eps = 1e-8;
int lowbit(int x) { return (x & (-x)); }
int ls(int u) { return u << 1; }
int rs(int u) { return u << 1 | 1; }

//+---------------------------------------------------------------------------------------------+
inline int read() {
	int x = 0, f = 0;
	char ch = 0;
	while (!isdigit(ch)) {
		f |= (ch == '-');
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return f ? -x : x;
}
//+----------------------------------------------------------------------------------------------+

struct node {
	int l, r;
	int v,tag;
}w[N<<2];

void pushu(int u) {
	w[u].v = w[ls(u)].v + w[rs(u)].v;
}

void maket(int u) {
	w[u].v = (w[u].r - w[u].l + 1) - w[u].v;
	w[u].tag ^= 1;
}

void pushd(int u) {
	if (w[u].tag == 0)return;
	maket(ls(u)); maket(rs(u));
	w[u].tag ^= 1;
}

void updata(int u,int l,int r) {
	if (l <= w[u].l && w[u].r <= r) {
		maket(u); return;
	}
	int mid = w[u].l + w[u].r >> 1;
	pushd(u);
	if (l <= mid)updata(ls(u), l, r);
	if (r > mid)updata(rs(u), l, r);
	pushu(u);
}

int query(int u, int l, int r) {
	if (l <= w[u].l && w[u].r <= r) {
		return w[u].v;
	}
	int res = 0, mid = w[u].l + w[u].r >> 1;
	pushd(u);
	if (l <= mid)res+=query(ls(u), l, r);
	if(r > mid)res += query(rs(u), l, r);
	return res;
}

void build(int u,int l,int r) {
	w[u].l = l, w[u].r = r; w[u].v = 0; w[u].tag = 0;
	if (l == r)return;
	int mid = l + r >> 1;
	build(ls(u), l, mid); build(rs(u), mid + 1, r);
	pushu(u);
}

int n, m;
int main() {
	n = read(); m = read();
	int op, l, r;
	build(1, 1, n);
	while (m--) {
		op = read(); l = read(); r = read();
		if (op == 0) {
			updata(1, l, r);
		}
		else {
			printf("%d\n", query(1, l, r));			
		}
	}

	return 0;
}

C++ 解法, 执行用时: 195ms, 内存消耗: 1608K, 提交时间: 2022-02-27 21:33:51

#include <iostream>
const int N = 1e5 + 10;
int n, m, a[N], d[N << 2], b[N << 2];

void pushdown(int s, int t, int p) {
	int l = p * 2, r = p * 2 + 1, m = (s + t) >> 1;
	if (b[p]) {
		b[l] ^= 1;
		b[r] ^= 1;
		d[l] = m - s + 1 - d[l];
		d[r] = t - m - d[r];
		b[p] = 0;
	}
	return ;
}

void modify(int l, int r, int s, int t, int p) {
	int m = (s + t) >> 1;
	if (l <= s && t <= r) {
		d[p] = t - s + 1 - d[p];
		b[p] ^= 1;
		return ;
	}
	pushdown(s, t, p);
	if (l <= m) modify(l, r, s, m, p * 2);
	if (m < r) modify(l, r, m + 1, t, p * 2 + 1);
	d[p] = d[p * 2] + d[p * 2 + 1];
}

int query(int l, int r, int s, int t, int p) {
	int m = (s + t) >> 1, ans = 0;
	if (l <= s && t <= r) return d[p];
	pushdown(s, t, p);
	if (l <= m) ans += query(l, r, s, m, p * 2);
	if (m < r) ans += query(l, r, m + 1, t, p * 2 + 1);
	return ans;
}

int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
	std::cin >> n >> m;
	while (m--) {
		int op1, op2, op3;
		std::cin >> op1 >> op2 >> op3;
		if (!op1) modify(op2, op3, 1, n, 1);
		else if (op1) std::cout << query(op2, op3, 1, n, 1) << std::endl; 
	}
	return 0;
}