python/TangDou/AcWing/SegmentTree/CF915E_Dynamic_XDS.cpp

#include <bits/stdc++.h>

using namespace std;
#define N 15000010 // 1.5e7=3e5*25*2,log 3e5=25
int n, q;

// 动态开点线段树
#define ls tr[u].l
#define rs tr[u].r
struct Node {
    int l, r;
    int sum, tag;
} tr[N];

int root, idx;

// 汇总统计信息
void pushup(int u) {
    tr[u].sum = tr[ls].sum + tr[rs].sum;
}

void pushdown(int &u, int l, int r) {
    if (tr[u].tag == -1) return;
    // 如果存在懒标记
    // 准备左右儿子
    if (ls == 0) ls = ++idx; // 没有左儿子，创建,因为传递的是地址符&,所以会回写tr[u].l
    if (rs == 0) rs = ++idx; // 没有右儿子，创建,因为传递的是地址符&,所以会回写tr[u].r
    // 懒标记下传
    int mid = (l + r) >> 1;
    tr[ls].sum = tr[u].tag * (mid - l + 1); // 区间和增加=懒标记 乘以 区间长度
    tr[ls].tag = tr[u].tag;                 // 加法的懒标记可以叠加
    tr[rs].sum = tr[u].tag * (r - mid);     // 区间和增加=懒标记 乘以 区间长度
    tr[rs].tag = tr[u].tag;                 // 加法的懒标记可以叠加
    // 清除懒标记
    tr[u].tag = -1;
}

// 区间修改
void modify(int &u, int l, int r, int L, int R, int v) {
    if (u == 0) u = ++idx, tr[u].tag = -1; // 动态开点，同时，将懒标记修改为-1，初始化
    if (L <= l && r <= R) {                // 完整覆盖
        tr[u].tag = v;                     // 懒标记赋值
        tr[u].sum = v * (r - l + 1);       // 记录sum
        return;                            // 返回节点号
    }

    pushdown(u, l, r);                         // 下放懒标记
    int mid = (l + r) >> 1;                    // 分裂
    if (L <= mid) modify(ls, l, mid, L, R, v); // 与左儿子区间有交集，递归修改左儿子
    if (mid < R) modify(rs, mid + 1, r, L, R, v);
    pushup(u);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("CF915E.in", "r", stdin);
#endif
    scanf("%d%d", &n, &q);
    modify(root, 1, n, 1, n, 1);
    int l, r, op;
    for (int i = 1; i <= q; i++) {
        scanf("%d%d%d", &l, &r, &op);
        if (op == 1) {
            modify(root, 1, n, l, r, 0); // 更新对应区间
            printf("%d\n", tr[1].sum);   // 1号节点表示区间(1,n)
        } else {
            modify(root, 1, n, l, r, 1);
            printf("%d\n", tr[1].sum);
        }
    }
    return 0;
}