1690 开关灯

USACO

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 Description

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

开始时全都关着，所以可以不用build建树（以为开始时亮着），维护更新时可以用！，1变0，0变1。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 #define lson l,m,rt<<1
 5 #define rson m+1,r,rt<<1|1
 6 #define MAXN 100100
 7 int n,t;
 8 int sum[MAXN<<2];
 9 int add[MAXN<<2];
10 
11 void putup(int rt)
12 {
13     sum[rt] = sum[rt<<1] + sum[rt<<1|1];
14 }
15 void putdown(int rt,int len)
16 {
17     if (add[rt])
18     {
19         add[rt<<1] = !add[rt<<1];
20         add[rt<<1|1] = !add[rt<<1|1];
21         sum[rt<<1] = (len-(len>>1))-sum[rt<<1];
22         sum[rt<<1|1] = (len>>1)-sum[rt<<1|1];
23         add[rt] = 0;
24     }
25 }
26 void update(int l,int r,int rt,int L,int R)
27 {
28     if (L<=l && r<=R)
29     {
30         add[rt] = !add[rt];
31         sum[rt] = r-l+1-sum[rt];
32         return ;
33     }
34     putdown(rt,r-l+1);
35     int m = (l+r)>>1;
36     if (L<=m) update(lson,L,R);
37     if (R>m)  update(rson,L,R);
38     putup(rt);
39 }
40 int query(int l,int r,int rt,int L,int R)
41 {
42     if (L<=l && r<=R)
43     {
44         return sum[rt];
45     }
46     putdown(rt,r-l+1);
47     int m = (l+r)>>1;
48     int ret = 0;
49     if (L<=m) ret += query(lson,L,R);
50     if (R>m)  ret += query(rson,L,R);
51     return ret;
52 }
53 int main()
54 {
55     scanf("%d%d",&n,&t);
56     while (t--)
57     {
58         int o,x,y;
59         scanf("%d%d%d",&o,&x,&y);
60         if (o==0) update(1,n,1,x,y);
61         else printf("%d
",query(1,n,1,x,y));    }
62     return 0;
63 }