洛谷 P3870 [TJOI2009] 开关 题解 线段树

[TJOI2009] 开关

题目描述

现有 $n$ 盏灯排成一排，从左到右依次编号为：$1$，$2$，……，$n$。然后依次执行 $m$ 项操作。

操作分为两种：

1. 指定一个区间 $[a,b]$，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开）；
2. 指定一个区间 $[a,b]$，要求你输出这个区间内有多少盏灯是打开的。

灯在初始时都是关着的。

输入格式

第一行有两个整数 $n$ 和 $m$，分别表示灯的数目和操作的数目。

接下来有 $m$ 行，每行有三个整数，依次为：$c$、$a$、$b$。其中 $c$ 表示操作的种类。

• 当 $c$ 的值为 $0$ 时，表示是第一种操作。
• 当 $c$ 的值为 $1$ 时，表示是第二种操作。

$a$ 和 $b$ 则分别表示了操作区间的左右边界。

输出格式

每当遇到第二种操作时，输出一行，包含一个整数，表示此时在查询的区间中打开的灯的数目。

样例 #1

样例输入 #1

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

样例输出 #1

1
2

数据规模与约定

对于全部的测试点，保证 $2\le n\le 10^5$，$1\le m\le 10^5$，$1\le a,b\le n$， c ∈ { 0 , 1 } c\in\{0,1\} c∈{0,1}。

原题

洛谷P3870——传送门

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template <typename T>
class SegTreeLazyRangeSet
{
    vector<T> tree, lazy;
    vector<T> *arr;
    int n, root, n4, end;

    void modify(int cl, int cr, int p) // 翻转该结点对应区间所有灯的状态
    {
        tree[p] = cr - cl + 1 - tree[p]; // 把该区间的灯状态翻转，相当于：当前开着的灯的数量=灯的总数-上一状态下开着的灯的数量
        lazy[p] ^= 1;                    // 更新懒标记
    }

    void maintain(int cl, int cr, int p) // 懒标记下传
    {
        int cm = cl + (cr - cl) / 2;
        if (cl != cr && lazy[p])
        {
            modify(cl, cm, p << 1);         // 下传懒标记给左孩子
            modify(cm + 1, cr, p << 1 | 1); // 下传懒标记给右孩子
            lazy[p] = 0;                    // 清空该结点懒标记
        }
    }

    T range_sum(int l, int r, int cl, int cr, int p)
    {
        if (l <= cl && cr <= r)
            return tree[p];
        int m = cl + (cr - cl) / 2;
        T sum = 0;
        maintain(cl, cr, p);
        if (l <= m)
            sum += range_sum(l, r, cl, m, p * 2);
        if (r > m)
            sum += range_sum(l, r, m + 1, cr, p * 2 + 1);
        return sum;
    }

    void range_set(int l, int r, T val, int cl, int cr, int p)
    {
        if (l <= cl && cr <= r)
        {
            modify(cl, cr, p);
            return;
        }
        int m = cl + (cr - cl) / 2;
        maintain(cl, cr, p);
        if (l <= m)
            range_set(l, r, val, cl, m, p * 2);
        if (r > m)
            range_set(l, r, val, m + 1, cr, p * 2 + 1);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

    void build(int s, int t, int p)
    {
        if (s == t)
        {
            tree[p] = (*arr)[s];
            return;
        }
        int m = s + (t - s) / 2;
        build(s, m, p * 2);
        build(m + 1, t, p * 2 + 1);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

public:
    explicit SegTreeLazyRangeSet<T>(vector<T> v)
    {
        n = v.size();
        n4 = n * 4;
        tree = vector<T>(n4, 0);
        lazy = vector<T>(n4, 0);
        arr = &v;
        end = n - 1;
        root = 1;
        build(0, end, 1);
        arr = nullptr;
    }

    T range_sum(int l, int r) { return range_sum(l, r, 0, end, root); }

    void range_set(int l, int r, int val) { range_set(l, r, val, 0, end, root); }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<int> a(n, 0);
    SegTreeLazyRangeSet<int> Stree(a);
    while (m--)
    {
        int c, a, b;
        cin >> c >> a >> b;
        // 线段树内的下标是从0到n-1，所以需要a--，b--来对应
        a--;
        b--;
        if (c == 0)
            Stree.range_set(a, b, 0);
        else
            cout << Stree.range_sum(a, b) << '\n';
    }

    return 0;
}