BZOJ 1230: [Usaco2008 Nov]lites 开关灯 (线段树区间修改，区间查询)
1230: [Usaco2008 Nov]lites 开关灯
Time Limit: 10 Sec Memory Limit: 162 MB Submit: 1676 Solved: 874 [Submit][Status][Discuss]
Description
Farmer John尝试通过和奶牛们玩益智玩具来保持他的奶牛们思维敏捷. 其中一个大型玩具是牛栏中的灯. 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之间的灯有多少是亮着的. 帮助FJ确保他的奶牛们可以得到正确的答案.
Input
第 1 行: 用空格隔开的两个整数N和M
第 2..M+1 行: 每行表示一个操作, 有三个用空格分开的整数: 指令号, S_i 和 E_i
Output
第 1..询问的次数 行: 对于每一次询问, 输出询问的结果.
Sample Input
4 5 0 1 2 0 2 4 1 2 3 0 2 4 1 1 4输入解释: 一共有4盏灯; 5个指令. 下面是执行的情况: 灯 1 2 3 4 Init: O O O O O = 关 * = 开 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的范围内有多少灯是亮的
Sample Output
1 2
考虑一次翻转对区间[L,R]的贡献
开着的灯数等于当前区间长度减去之前区间[L,R]内开着的灯数
也就是tree[rt].sum = r-l+1-tree[rt].sum;
对于lazy标记，无非是从0变到1，从1变到0.
手误写错了一个地方，2A
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月01日 星期三 09时51分31秒
4File Name :1230.cpp
5************************************************ */
6
7#include <bits/stdc++.h>
8#define PB push_back
9#define fst first
10#define sec second
11#define lson l,m,rt<<1
12#define rson m+1,r,rt<<1|1
13#define ms(a,x) memset(a,x,sizeof(a))
14typedef long long LL;
15#define pi pair < int ,int >
16#define MP make_pair
17
18using namespace std;
19const double eps = 1E-8;
20const int dx4[4]={1,0,0,-1};
21const int dy4[4]={0,-1,1,0};
22const int inf = 0x3f3f3f3f;
23const int N=1E5+7;
24int n,m;
25struct Tree
26{
27 int lazy;
28 int sum;
29}tree[N<<2];
30void PushDown(int l,int r,int rt)
31{
32 if (tree[rt].lazy)
33 {
34 int m = (l+r)>>1;
35 tree[rt<<1].lazy = 1- tree[rt<<1].lazy;
36 tree[rt<<1|1].lazy = 1- tree[rt<<1|1].lazy;
37 tree[rt<<1].sum = m-l+1-tree[rt<<1].sum;
38 tree[rt<<1|1].sum = r-m - tree[rt<<1|1].sum;
39 tree[rt].lazy = 0;
40 }
41}
42void PushUp( int rt)
43{
44 tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
45}
46void update(int L,int R,int l,int r,int rt)
47{
48 if (L<=l && r<=R)
49 {
50 tree[rt].sum = r-l+1 - tree[rt].sum;
51 tree[rt].lazy = 1-tree[rt].lazy;
52 return;
53 }
54 int m = (l+r)>>1;
55 PushDown(l,r,rt);
56 if (L<=m) update(L,R,lson);
57 if (R>=m+1) update(L,R,rson);
58 PushUp(rt);
59}
60int Query(int L, int R,int l,int r,int rt)
61{
62 if (L<=l && r<=R)
63 {
64 return tree[rt].sum;
65 }
66 int m = (l+r)>>1;
67 PushDown(l,r,rt);
68 int res = 0 ;
69 if (L<=m) res = Query(L,R,lson);
70 if (R>=m+1) res = res + Query(L,R,rson);
71 return res;
72}
73
74int main()
75{
76 #ifndef ONLINE_JUDGE
77 freopen("./in.txt","r",stdin);
78 #endif
79 ms(tree,0);
80 cin>>n>>m;
81 while (m--)
82 {
83 int opt,x,y;
84 scanf("%d %d %d",&opt,&x,&y);
85 if (opt==0) update(x,y,1,n,1);
86 else printf("%d\n",Query(x,y,1,n,1));
87 }
88 #ifndef ONLINE_JUDGE
89 fclose(stdin);
90 #endif
91 return 0;
92}