24.CF915E Physical Education Lessons 线段树维护区间反转

24.CF915E Physical Education Lessons 线段树维护区间反转

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给定 0 0 0序列要求支持区间 0 − 1 0-1 0−1反转，区间求和(容斥一下)

对原题可以发现容斥一下，初始全0表示全为休息日，然后打标记支持区间反转即可。

洛谷传送门：CF915E Physical Education Lessons - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：E. Physical Education Lessons (codeforces.com)

题目分析

大水题。

原题要求支持对全 0 0 0序列的区间反转，初始全 0 0 0表示全为休息日，然后打标记支持区间反转即可。

实在是没啥可分析的，太简单了…直接按照区间反转的套路来就可以：建树初始化标记为 − 1 -1 −1，然后下放容斥即可。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define endl '\n'
using namespace std;

const int N = 15001000, MOD = 1e9 + 7;

namespace SegTree{
    #define ls lc[rt]
    #define rs rc[rt]
    #define lson ls, l, mid
    #define rson rs, mid + 1, r

    int tree[N], lazy[N], lc[N], rc[N], tot;

    void build(){ memset(lazy, -1, sizeof(lazy)); }

    void push_up(int rt){ tree[rt] = tree[ls] + tree[rs]; }

    void push_down(int rt, int m){
        if(lazy[rt] == -1) return;
        if(!ls) ls = ++tot;
        if(!rs) rs = ++tot;
        tree[ls] = lazy[rt] * (m - (m >> 1));
        tree[rs] = lazy[rt] * (m >> 1);
        lazy[ls] = lazy[rs] = lazy[rt];
        lazy[rt] = -1;
    }

    void update(int &rt, int l, int r, int L, int R, int val){
        if(!rt) rt = ++tot;
        if(l >= L && r > 1;
        if(mid >= L) update(lson, L, R, val);
        if(mid = L && r > 1, ans = 0;
        if(mid >= L) ans += query(lson, L, R);
        if(mid > n >> q;
    SegTree::build();
    for(int i = 1; i > l >> r >> k;
        if(k == 1){
            SegTree::update(root, 1, n, l, r, 1);
        } else {
            SegTree::update(root, 1, n, l, r, 0);
        }
        cout