LITES - Bật đèn

Tác giả: skyvn97

Ngôn ngữ: C++

#include<cstdio>
#define MAX   100100
int t[5*MAX];
int c[5*MAX];
int m,n;
void init(void) {
	scanf("%d",&n);
	scanf("%d",&m);	
	int i;
	for (i=1;i<=4*n;i=i+1) {
		t[i]=0;
		c[i]=0;
	}
}
void update(int i,int l,int r,int u,int v) {
	//printf("Updating %d %d %d %d %d\n",i,l,r,u,v);
	if (l>v) return;
	if (r<u) return;
	if (l>r) return;
	if (u<=l && r<=v) {
		c[i]=1-c[i];
		t[i]=r-l+1-t[i];
		//printf("   t[%d]=%d c[%d]=%d\n",i,t[i],i,c[i]);
		return;
	}
	if (c[i]>0) c[2*i]=1-c[2*i];
	if (c[i]>0) c[2*i+1]=1-c[2*i+1];
	int m=(l+r)/2;
	if (c[i]>0) t[2*i]=m-l+1-t[2*i];
	if (c[i]>0) t[2*i+1]=r-m-t[2*i+1];	
	c[i]=0;
	//printf("   t[%d]=%d c[%d]=%d\n",2*i,t[2*i],2*i,c[2*i]);
	//printf("   t[%d]=%d c[%d]=%d\n",2*i+1,t[2*i+1],2*i+1,c[2*i+1]);
	update(2*i,l,m,u,v);
	update(2*i+1,m+1,r,u,v);
	t[i]=t[2*i]+t[2*i+1];
}
int sum(int i,int l,int r,int u,int v,int change) {
	//printf("Geting sum %d %d %d %d %d with %d\n",i,l,r,u,v,change);
	if (l>v) return (0);
	if (r<u) return (0);
	if (l>r) return (0);
	if (u<=l && r<=v) {
		if (change>0) return (r-l+1-t[i]);
		else return (t[i]);
	}
	if (c[i]>0) change=1-change;
	int m=(l+r)/2;
	int left=sum(2*i,l,m,u,v,change);
	int right=sum(2*i+1,m+1,r,u,v,change);
	return (left+right);
}
void process(void) {
	int i,s,e,T;
	//int j;
	for (i=1;i<=m;i=i+1) {
		scanf("%d",&T);
		scanf("%d",&s);
		scanf("%d",&e);
		if (T==0) {
			update(1,1,n,s,e);
			//printf("After update %d %d\n",s,e);
			//for (j=1;j<=7;j=j+1) printf("%d ",t[j]); printf("\n");
			//for (j=1;j<=7;j=j+1) printf("%d ",c[j]); printf("\n");
		}
		else printf("%d\n",sum(1,1,n,s,e,0));
	}	
}
int main(void) {
	//freopen("tmp.txt","r",stdin);
	init();
	process();
	return 0;
}

Download