NOI2009 开关

NOI2009 开关

现有N（2 ≤ N ≤ 100000）盏灯排成一排，从左到右依次编号为：1，2，......，N。然后依次执行M（1 ≤ M ≤ 100000）项操作，操作分为两种：第一种操作指定一个区间[a, b]，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开），第二种操作是指定一个区间[a, b]，要求你输出这个区间内有多少盏灯是打开的。灯在初始时都是关着的。

两种操作分别是区间更改（取反）和区间查询。这道题无疑是用线段树做。

需要特别去想的是，延迟标记向下传递的时候，当前节点的懒标记若存在，则表示区间需要取反，更新的sum是用区间总数减去之前的灯数。

 1 #include<iostream>
 2 using namespace std;
 3 const int SIZE = 100005;
 4 struct SegmentTree{
 5     int l, r, sum;
 6     bool p;
 7 }t[SIZE * 4];
 8 void build(int p, int l, int r){
 9     t[p].l = l, t[p].r = r;
10     if(l == r) return;
11     int mid = (l + r) >> 1;
12     build(p*2, l, mid);
13     build(p*2+1, mid+1, r);
14 }
15 
16 void spread(int p){
17     if(t[p].p){
18         t[p*2].sum = t[p*2].r-t[p*2].l+1 - t[p*2].sum;
19         t[p*2+1].sum = t[p*2+1].r-t[p*2+1].l+1 - t[p*2+1].sum;
20         t[p*2].p = !t[p*2].p;
21         t[p*2+1].p = !t[p*2+1].p;
22         t[p].p = 0;
23     }
24 }
25 void change(int p, int l, int r){
26     if(l <= t[p].l && r >= t[p].r) {
27         t[p].p = !t[p].p;
28         t[p].sum = t[p].r-t[p].l+1 - t[p].sum;
29         return;
30     }    
31     spread(p);
32     int mid = (t[p].l + t[p].r) >> 1;
33     if (l <= mid) change(p*2, l, r);
34     if(r > mid) change(p*2+1, l, r);
35     t[p].sum = t[p*2].sum + t[p*2+1].sum;
36 }
37 
38 int ask(int p, int l, int r){
39     if(l <= t[p].l && r >= t[p].r){
40         return t[p].sum;
41     }
42     spread(p);
43     int mid = (t[p].l + t[p].r) >> 1;
44     int val = 0;
45     if(l <= mid) val += ask(p*2, l, r);
46     if(r > mid) val += ask(p*2+1, l, r);
47     return val;
48 }
49 
50 int main(){
51     int n, m;
52     cin >> n >> m;
53     build(1, 1, n);
54     while(m--){
55         int f, x, y;
56         cin >> f >> x >> y;
57         switch(f){
58             case 0:
59                 change(1, x, y);
60                 break;
61             case 1:
62                 cout << ask(1, x, y) <<"
";
63                 break;
64         }
65     }
66     
67     
68     
69     return 0;
70 }