LITES - Bật đèn

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 100040;

int sum[MAXN * 4], flip[MAXN * 4];

void update(int n, int l, int r, int x, int y) {
	if(x<=l && r<=y) {
		flip[n] ^= 1;
		sum[n] = (r-l+1) - sum[n];
		return;
	}
	int m = (l+r) / 2;
	if(x<=m) update(2*n,l,m,x,y);
	if(m<y) update(2*n+1,m+1,r,x,y);
	sum[n] = sum[2*n] + sum[2*n+1];
	if(flip[n]) sum[n] = (r-l+1) - sum[n];
}

int getsum(int n, int l, int r, int x, int y, int f) {
	if(x<=l && r<=y) {
		if(f) return (r-l+1) - sum[n];
		else return sum[n];
	}
	int m = (l+r) / 2;
	f ^= flip[n];
	int res = 0;
	if(x<=m) res += getsum(2*n,l,m,x,y,f);
	if(m<y) res += getsum(2*n+1,m+1,r,x,y,f);
	f ^= flip[n];
	return res;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=0;i<m;++i) {
		int c, u, v;
		scanf("%d%d%d", &c, &u, &v);
		if(c==0) update( 1, 1, n, u, v);
		else printf("%d\n", getsum( 1, 1, n, u, v, 0));
	}
	return 0;
}

Download