题解 P3870 【[TJOI2009]开关】

Nero_Claudius · 2018-05-12 00:29:32 · 题解

又是一道线段树。。。

本题其实是一道裸题。。。不明白为什么是这个难度标签。

思路很明显，用tree[i].val表示区间内开着的灯的数量。

然后常规操作（建树、查询、修改）就可以了。

最后：lazy tag是个好东西。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define lson pos << 1
#define rson pos << 1 | 1
using namespace std;

const int maxn = 100100;

int n, m, c, a, b;

struct node {
    int l,r;
    int val;          
    int lazy;
} tree[maxn << 2];

inline void Pushup(int pos) {
    tree[pos].val = tree[lson].val + tree[rson].val;
}

void Pushdown(int pos) {
    if(tree[pos].lazy) {
        tree[lson].lazy ^= 1; 
        tree[rson].lazy ^= 1;
        tree[lson].val = tree[lson].len() - tree[lson].val;
        tree[rson].val = tree[rson].len() - tree[rson].val;
        tree[pos].lazy = 0;
    }
}

void Build(int l, int r, int pos) {  
    tree[pos].l = l;
    tree[pos].r = r;
    tree[pos].val = 0;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    Build(l, mid, lson);
    Build(mid + 1, r, rson);
}

void Update(int l, int r, int pos) {
    if(l <= tree[pos].l && tree[pos].r <= r) {
        tree[pos].val = tree[pos].len() - tree[pos].val;
        tree[pos].lazy ^= 1;
        return ;
    }
    Pushdown(pos);
    int mid = tree[pos].mid();
    if(l <= mid) Update(l, r, lson);
    if(r > mid) Update(l, r, rson);
    Pushup(pos);
}

int Query(int l, int r, int pos) {
    if(l <= tree[pos].l && tree[pos].r <= r) {
        return tree[pos].val;
    }
    Pushdown(pos);
    int mid = tree[pos].mid();
    int ans = 0;
    if(l <= mid)  ans += Query(l, r, lson);
    if(r > mid)   ans += Query(l, r, rson);
    return ans;
}

int main() {
    cin >> n >> m;
    Build(1, n, 1);
    while(m--) {
        cin >> c >> a >> b;
        if(c == 0) {
            Update(a, b, 1);
        } else {
            cout << Query(a, b, 1) << endl;
        }
    }
}

话说回来。。。这道题好像在洛谷上有不知一道重题，可以n倍经验了！！