526互联

P3870 [TJOI2009] 开关

发布时间 2024-01-10 00:31:22作者: 纯粹的

原题链接

题记

就是线段树，不过树和延迟标记有点绕

code

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

struct SegmentTree
{
    vector<int> tree, lazy;//tree代表这个节点开着灯的数量，lazy代表这个节点是否需要整体改变，当这个节点的区间连续开关两次等于没开
    int n;

    SegmentTree(int size) : n(size)//说实话，我让gpt生成的，我也看不懂，就当初始化操作吧
    {
        tree.resize(4 * size);
        lazy.resize(4 * size, 0);
    }

    void updateRange(int node, int start, int ends, int l, int r)
    {
        if (lazy[node])//改变该节点前看看有没有这个节点积累的、需要被改变的，但是还没改变的。
        {
            tree[node] = (ends - start + 1) - tree[node];
            if (start != ends)//一个节点改变后，其子节点也应全部改变，只因还没用到，所以打个延迟标记，等用到了再改变
            {
                lazy[node * 2] ^= 1;//积累传给子节点
                lazy[node * 2 + 1] ^= 1;
            }
            lazy[node] = 0;//清零
        }

        if (start > ends || start > r || ends < l) return;//如果该节点的范围与所求范围完全不沾边

        if (start >= l && ends <= r)//如果该节点的范围被所求范围完全包裹
        {
            tree[node] = (ends - start + 1) - tree[node];
            if (start != ends)
            {
                lazy[node * 2] ^= 1;
                lazy[node * 2 + 1] ^= 1;
            }
            return;//需要的是整体。就不需要细分了
        }

        int mid = (start + ends) / 2;
        updateRange(node * 2, start, mid, l, r);
        updateRange(node * 2 + 1, mid + 1, ends, l, r);

        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    int queryRange(int node, int start, int ends, int l, int r)
    {
        if (start > ends || start > r || ends < l) return 0;

        if (lazy[node])//先看有没有积累
        {
            tree[node] = (ends - start + 1) - tree[node];

            if (start != ends)
            {
                lazy[node * 2] ^= 1;
                lazy[node * 2 + 1] ^= 1;
            }

            lazy[node] = 0;//清空
        }

        if (start >= l && ends <= r) return tree[node];

        int mid = (start + ends) / 2;
        int p1 = queryRange(node * 2, start, mid, l, r);
        int p2 = queryRange(node * 2 + 1, mid + 1, ends, l, r);

        return (p1 + p2);
    }
};
int main()
{
    int n, m;
    cin >> n >> m;
    SegmentTree st(n+5);//把函数放到结构体里面，很舒服
    for (int i = 0; i < m; i++)
    {
        int c, a, b;
        cin >> c >> a >> b;
        if (c == 0) st.updateRange(1, 1, n, a, b);
        else cout << st.queryRange(1, 1, n, a, b) << endl;
    }
    return 0;
}