LITES - Bật đèn

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5;
int tree[4*N], com[4*N], n;

void update(int x, int y, int k = 0, int l = 0, int r = n) {
	if(r <= l || r <= x || y <= l) return;
	if(x <= l && r <= y) ++com[k], tree[k] = r-l-tree[k];
	else {
		update(x, y, 2*k+1, l, (l+r)/2);
		update(x, y, 2*k+2, (l+r)/2, r);
		tree[k] = tree[2*k+1] + tree[2*k+2];
		if(com[k] % 2 == 1) tree[k] = r-l-tree[k];
	}
}

int get(int x, int y, int k = 0, int l = 0, int r = n) {
	if(r <= l || r <= x || y <= l) return 0;
	if(x <= l && r <= y) return tree[k];
	int res = get(x, y, 2*k+1, l, (l+r)/2) + get(x, y, 2*k+2, (l+r)/2, r);
	return com[k] % 2 == 0 ? res : min(r, y) - max(l, x) - res;
}

int main() {
	int q; scanf("%d%d", &n, &q);
	while(q-- > 0) {
		int t, x, y; scanf("%d%d%d", &t, &x, &y);
		if(t == 0) update(x-1, y);
		else printf("%d\n", get(x-1, y));
	}
	return 0;
}

Download