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;
}