Codevs_1690_开关灯_(线段树)

描述

---

http://codevs.cn/problem/1690/

一排共 n 个灯,起初都是关着的,现在有 m 次操作. 0 开头的操作代表将 l ~ r 的开关按一遍,1 开头的操作代表询问 l ~ r 共多少个开着的灯.

1690 开关灯

USACO

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 Description

YYX家门前的街上有N(2<=N<=100000)盏路灯，在晚上六点之前，这些路灯全是关着的，六点之后，会有M(2<=m& lt;=100000)个人陆续按下开关，这些开关可以改变从第i盏灯到第j盏灯的状态，现在YYX想知道，从第x盏灯到第y盏灯中有多少是亮着的(1& lt;=i,j,x,y<=N)

输入描述 Input Description

第 1 行: 用空格隔开的两个整数N和M

第 2..M+1 行: 每行表示一个操作, 有三个用空格分开的整数: 指令号(0代表按下开关，1代表询问状态), x 和 y 

输出描述 Output Description

第 1..询问总次数 行:对于每一次询问，输出询问的结果

样例输入 Sample Input

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

样例输出
Sample Output

1
2

数据范围及提示
Data Size & Hint

一共4盏灯，5个操作，下面是每次操作的状态(X代表关上的，O代表开着的)：

XXXX -> OOXX -> OXOO -> 询问1~3 -> OOXX -> 询问1~4

分析

---

刚开始想的是用 0 , 1 , -1 分别代表区间都是关着的,都是开着的,有开的又有关的,跟新和查询的时候都是查找到非 -1 的区间再做处理,但是 TLE 了.

想一下如果灯是 1 0 1 0 1 0 1 0 1...这样排列的,那就退化得不成样子了.

所以用 on 和 off 分别代表区间内开着的和关着的等的数量,如果按开关,就把这两个值交换.

最后可以不用 off ,只用一个 on ,可以通过区间长度进行计算.

 #include<cstdio>

 const int maxn=;
 struct node { int l,r; int on;bool d; }a[*maxn];
 int n,m;

 void build_tree(int l,int r,int k)
 {
     a[k].l=l; a[k].r=r; a[k].on=; a[k].d=false;
     if(l==r) return;
     int mid=l+(r-l)/;
     build_tree(l,mid,*k);
     build_tree(mid+,r,*k+);
 }

 inline void turn(int k)
 {
     a[k].on=(a[k].r-a[k].l+)-a[k].on;
     a[k].d^=true;
 }

 void update(int l,int r,int k)
 {
     if(a[k].l==l&&a[k].r==r)
     {
         turn(k);
         return;
     }
     if(a[k].d)
     {
         turn(*k);
         turn(*k+);
         a[k].d=false;
     }
     int mid=a[k].l+(a[k].r-a[k].l)/;
     if(r<=mid) update(l,r,*k);
     else if(l>mid) update(l,r,*k+);
     else { update(l,mid,*k); update(mid+,r,*k+); }
     a[k].on=a[*k].on+a[*k+].on;
 }

 int search(int l,int r,int k)
 {
     if(a[k].l==l&&a[k].r==r) return a[k].on;
     if(a[k].d)
     {
         turn(*k);
         turn(*k+);
         a[k].d=false;
     }
     int mid=a[k].l+(a[k].r-a[k].l)/;
     if(r<=mid) return search(l,r,*k);
     else if(l>mid) return search(l,r,*k+);
     else return search(l,mid,*k)+search(mid+,r,*k+);
 }

 int main()
 {
     scanf("%d%d",&n,&m);
     build_tree(,n,);

     int qry,l,r;
     for(int i=;i<=m;i++)
     {
         scanf("%d%d%d",&qry,&l,&r);
         switch(qry)
         {
             case :
                 update(l,r,);
                 break;
             case :
                 printf("%d\n",search(l,r,));
                 break;
         }
     }
     return ;
 }