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
/* ***********************************************
Author :111qqz
Created Time :2017年11月01日 星期三 09时51分31秒
File Name :1230.cpp
************************************************ */
1#include <bits/stdc++.h>
2#define PB push_back
3#define fst first
4#define sec second
5#define lson l,m,rt<<1
6#define rson m+1,r,rt<<1|1
7#define ms(a,x) memset(a,x,sizeof(a))
8typedef long long LL;
9#define pi pair < int ,int >
10#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7int n,m;
8struct Tree
9{
10 int lazy;
11 int sum;
12}tree[N<<2];
13void PushDown(int l,int r,int rt)
14{
15 if (tree[rt].lazy)
16 {
17 int m = (l+r)>>1;
18 tree[rt<<1].lazy = 1- tree[rt<<1].lazy;
19 tree[rt<<1|1].lazy = 1- tree[rt<<1|1].lazy;
20 tree[rt<<1].sum = m-l+1-tree[rt<<1].sum;
21 tree[rt<<1|1].sum = r-m - tree[rt<<1|1].sum;
22 tree[rt].lazy = 0;
23 }
24}
25void PushUp( int rt)
26{
27 tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
28}
29void update(int L,int R,int l,int r,int rt)
30{
31 if (L<=l && r<=R)
32 {
33 tree[rt].sum = r-l+1 - tree[rt].sum;
34 tree[rt].lazy = 1-tree[rt].lazy;
35 return;
36 }
37 int m = (l+r)>>1;
38 PushDown(l,r,rt);
39 if (L<=m) update(L,R,lson);
40 if (R>=m+1) update(L,R,rson);
41 PushUp(rt);
42}
43int Query(int L, int R,int l,int r,int rt)
44{
45 if (L<=l && r<=R)
46 {
47 return tree[rt].sum;
48 }
49 int m = (l+r)>>1;
50 PushDown(l,r,rt);
51 int res = 0 ;
52 if (L<=m) res = Query(L,R,lson);
53 if (R>=m+1) res = res + Query(L,R,rson);
54 return res;
55}
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("./in.txt","r",stdin);
5 #endif
6 ms(tree,0);
7 cin>>n>>m;
8 while (m--)
9 {
10 int opt,x,y;
11 scanf("%d %d %d",&opt,&x,&y);
12 if (opt==0) update(x,y,1,n,1);
13 else printf("%d\n",Query(x,y,1,n,1));
14 }
15 #ifndef ONLINE_JUDGE
16 fclose(stdin);
17 #endif
18 return 0;
19}