线段树的应用一中模拟lites

开关灯
源文件：    lites.cpp/.c/.pas
输入文件：    lites.in
输出文件：    lites.out
时限：        1s
空间：     256M
【题目描述】
小Y尝试通过和奶牛们玩益智玩具来保持他的奶牛们思维敏捷，其中一个大型玩具是牛栏中的灯。
N (2<= N <= 100,000) 头奶牛中的每一头被连续的编号为1..N, 站在一个彩色的灯下面。刚到傍晚的时候, 所有的灯都是关闭的。奶牛们通过N个按钮来控制灯的开关，按第i个按钮可以改变第i个灯的状态。
奶牛们执行M (1<= M <= 100,000)条指令, 每个指令都是两个整数中的一个(0<= 指令号<= 1)。
第1种指令(用0表示)包含两个数字S_i和E_i (1<= S_i<= E_i<= N), 它们表示起始开关和终止开关。奶牛们只需要把从S_i到E_i之间的按钮都按一次, 就可以完成这个指令。
第2种指令(用1表示)同样包含两个数字S_i和E_i (1<= S_i<= E_i<= N), 不过这种指令是询问从S_i到E_i之间的灯有多少是亮着的。
请你帮助小Y确保他的奶牛们可以得到正确的答案。
【输入格式】
第 1 行: 用空格隔开的两个整数N和M。
第 2..M+1 行: 每行表示一个操作, 有三个用空格分开的整数: 指令号, S_i 和 E_i。
【输出格式】
对于每一次询问, 输出一行表示询问的结果。
【输入样例】
4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4
【输出样例】
1
2
【样例解释】
一共有4盏灯，5个指令。下面是执行的情况:
    灯
            1 2 3 4
Init:     O OOOO = 关* = 开
  0 1 2 ->  * * O O改变灯 1 和 2 的状态
  0 2 4 ->  * O * *
  1 2 3 ->  1        输出在2..3的范围内有多少灯是亮的
  0 2 4 ->  * * O O改变灯 2 ,3 和 4 的状态
  1 1 4 ->  2        输出在1..4的范围内有多少灯是亮的
【数据规模】
对于40%的数据满足：1<=N,M<=10000；
对于100%的数据满足： 1<=N,M<=100000。
    

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct node{
 4     int l,r,dat,lazy;
 5 }shu[400010];//结构体，中间的任何一个单独成为一个数组都是可以的，其实没有什么高大上的，只是看起来比较高逼格而已。
 6 int n,m,a,b,c,ans;//个人建议多设全局变量，Pascal的优良传统，比较方便，不容易错。
 7 void build_tree(int x,int y,int z){//建树，和昨天我的代码是一样的（不对，是今天）。
 8     shu[x].l=y;
 9     shu[x].r=z;
10     if (y==z) return;
11     int o=(y+z)/2; 
12     build_tree(x*2,y,o);
13     build_tree(x*2+1,o+1,z);
14 }
15 void caozuo(int x){//操作，为什么要单独在一个过程中呢？因为下面两段都要用到，更方便编程思路更清晰。
16     if (shu[x].lazy){//开灯的时候改变。也可以用bool数组。
17         shu[x*2].dat=(shu[x*2].r-shu[x*2].l+1)-shu[x*2].dat;//这是因为一部分是开的，那么改变了之后，另一部分就是开的，这一部分是关的。
18         shu[x*2+1].dat=(shu[x*2+1].r-shu[x*2+1].l+1)-shu[x*2+1].dat;
19         if (shu[x*2].lazy) shu[x*2].lazy=0;
20         else shu[x*2].lazy=1;
21         if (shu[x*2+1].lazy) shu[x*2+1].lazy=0;
22         else shu[x*2+1].lazy=1;
23         shu[x].lazy=0;//处理完了，lazy标记还原。
24     }
25 }
26 void add_tree(int x){
27     if (shu[x].l>=b&&shu[x].r<=c){
28         shu[x].dat=(shu[x].r-shu[x].l+1)-shu[x].dat;//两遍开就是关
29         if (shu[x].lazy) shu[x].lazy=0;
30         else shu[x].lazy=1;
31         return;
32     }
33     caozuo(x);
34     int o=(shu[x].l+shu[x].r)/2;
35     if(b<=o) add_tree(x*2);//如果中间数比要改变区间最左边大或相等，查找左子树。
36     if(c>o) add_tree(x*2+1);//如果中间数比要改变区间最右边小，查找右子树。
37     shu[x].dat=shu[x*2].dat+shu[x*2+1].dat;//更新父节点
38 }
39 void find_tree(int x){//查找区间和。
40     if (shu[x].l>=b&&shu[x].r<=c){//在要查区间内就加上对应区间和，不用往下找，因为子结点的区间在父节点的区间之内，不应该重复。
41         ans=ans+shu[x].dat;
42         return;
43     }
44     caozuo(x);
45     int o=(shu[x].l+shu[x].r)/2;
46     if(b<=o) find_tree(x*2);
47     if(c>o) find_tree(x*2+1);
48     return;
49 }
50 int main(){
51     scanf("%d%d",&n,&m);
52     build_tree(1,1,n);
53     for (int i=1;i<=m;i++){
54         scanf("%d%d%d",&a,&b,&c);
55         if (a==0){
56             add_tree(1);
57         }
58         else {
59             ans=0;
60             find_tree(1);
61             printf("%d\n",ans);
62         }
63     }
64     return 0;
65 }