萌新刚学线段树,10 分求调
查看原帖
萌新刚学线段树,10 分求调
809729
SJZ2010楼主2023/9/17 20:11

只 A 了 2,不知道哪里错了。

#include <cstdio>
#include <emmintrin.h>
#include <immintrin.h>

#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

typedef long long ll;

const int N = 1e5 + 5;

struct SegTree {
	int data[N << 2], tag[N << 2];
	
	inline void update(int l, int r, int s, int t, int now) {
		if (l <= s && t <= r) {
			tag[now] ^= 1;
			data[now] = tag[now] ? (t - s + 1 - data[now]) : data[now];
			if (s == t)
				tag[now] ^= 1;
			return;
		}
		register int mid = (s + t) >> 1;
		if (tag[now]) {
			if (t - s > 1)
				tag[now << 1] ^= 1, tag[(now << 1) | 1] ^= 1;
			data[now << 1] = (mid - s + 1 - data[now << 1]), data[(now << 1) | 1] = (t - mid - data[(now << 1) | 1]);
			tag[now] = 0;
		}
		if (l <= mid)
			update(l, r, s, mid, now << 1);
		if (r > mid)
			update(l, r, mid + 1, t, (now << 1) | 1);
		data[now] = data[now << 1] + data[(now << 1) | 1];
	}
	
	inline int query(int l, int r, int s, int t, int now) {
		if (l <= s && t <= r)
			return data[now];
		register int mid = (s + t) >> 1, sum(0);
		if (tag[now]) {
			if (t - s > 1)
				tag[now << 1] ^= 1, tag[(now << 1) | 1] ^= 1;
			data[now << 1] = (mid - s + 1 - data[now << 1]), data[(now << 1) | 1] = (t - mid - data[(now << 1) | 1]);
			tag[now] = 0;
		}
		if (l <= mid)
			sum += query(l, r, s, mid, now << 1);
		if (r > mid)
			sum += query(l, r, mid + 1, t, (now << 1) | 1);
		return sum;
	}
} Tree;

static int n, T, opt, a, b;

int main() {
	scanf("%d %d", &n, &T);
	while (T--) {
		scanf("%d %d %d", &opt, &a, &b);
		if (opt)
			printf("%d\n", Tree.query(a, b, 1, n, 1));
		else
			Tree.update(a, b, 1, n, 1);
	}
	return 0;
}
2023/9/17 20:11
加载中...