BZOJ 1230: [Usaco2008 Nov]lites 开关灯 (线段树区间修改，区间查询)

Nov 1, 2017 · 2 min read · lazy标记线段树

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
************************************************ */

#include <bits/stdc++.h>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
int n,m;
struct Tree
{
    int lazy;
    int sum;
}tree[N<<2];
void PushDown(int l,int r,int rt)
{
    if (tree[rt].lazy)
    {
    int m = (l+r)>>1;
    tree[rt<<1].lazy  = 1- tree[rt<<1].lazy;
    tree[rt<<1|1].lazy = 1- tree[rt<<1|1].lazy;
    tree[rt<<1].sum = m-l+1-tree[rt<<1].sum;
    tree[rt<<1|1].sum = r-m - tree[rt<<1|1].sum;
    tree[rt].lazy = 0;
    }
}
void PushUp( int rt)
{
    tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
}
void update(int L,int R,int l,int r,int rt)
{
    if (L<=l && r<=R)
    {
    tree[rt].sum = r-l+1 - tree[rt].sum;
    tree[rt].lazy  = 1-tree[rt].lazy;
    return;
    }
    int m = (l+r)>>1;
    PushDown(l,r,rt);
    if (L<=m) update(L,R,lson);
    if (R>=m+1) update(L,R,rson);
    PushUp(rt);
}
int Query(int L, int R,int l,int r,int rt)
{
    if (L<=l && r<=R)
    {
    return tree[rt].sum;
    }
    int m = (l+r)>>1;
    PushDown(l,r,rt);
    int res = 0 ;
    if (L<=m) res = Query(L,R,lson);
    if (R>=m+1) res = res + Query(L,R,rson);
    return res;
}

int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("./in.txt","r",stdin);
  #endif
    ms(tree,0);
    cin>>n>>m;
    while (m--)
    {
        int opt,x,y;
        scanf("%d %d %d",&opt,&x,&y);
        if (opt==0) update(x,y,1,n,1);
        else printf("%d\n",Query(x,y,1,n,1));
    }
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}