python/TangDou/AcWing/SegmentTree/CF915E.md

##[Physical Education Lessons](https://codeforces.com/contest/915/problem/E)

#### 题意：
Alex高中毕业了，他现在是大学新生。虽然他学习编程，但他还是要上体育课，这对他来说完全是一个意外。快要期末了，但是不幸的Alex的体育学分还是零蛋！

Alex可不希望被开除，他想知道到期末还有多少天的工作日，这样他就能在这些日子里修体育学分。但是在这里计算工作日可不是件容易的事情：

从现在到学期结束还有 $n$ 天(从 $1$ 到 $n$ 编号)，他们一开始都是工作日。接下来学校的工作人员会**依次**发出 $q$ 个指令，每个指令可以用三个参数 $l,r,k$ 描述：

- 如果 $k=1$，那么从 $l$ 到 $r$ （包含端点）的所有日子都变成**非**工作日。

- 如果 $k=2$，那么从 $l$ 到 $r$ （包含端点）的所有日子都变成**工作日**。

帮助Alex统计每个指令下发后，剩余的工作日天数。

#### 输入格式：

第一行一个整数 $n$，第二行一个整数 $q$ $(1\le n\le 10^9,\;1\le q\le 3\cdot 10^5)$，分别是剩余的天数和指令的个数。

接下来 $q$ 行，第 $i$ 行有 $3$ 个整数 $l_i,r_i,k_i$，描述第 $i$ 个指令 $(1\le l_i,r_i\le n,\;1\le k\le 2)$。

#### 输出格式：

输出 $q$ 行，第 $i$ 行表示第 $i$ 个指令被下发后剩余的工作日天数。

### 样例输入 #1

```
4
6
1 2 1
3 4 1
2 3 2
1 3 2
2 4 1
1 4 2
```

### 样例输出 #1

```
2
0
2
3
1
4
```
### 二、动态开点线段树解法

```cpp {.line-numbers}
#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 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 root;
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;
}
```

### 三、柯朵莉树解法
这题就是一道$ODT$的板子，操作是推平，查询是求和

**$Q$：这题不保证数据随机为什么还能用$ODT$?**

$A$：$hackODT$的方法是没有推平操作，但这题修改操作全是推平操作。

于是暴力很好写，但$CF$的毒瘤们不会让你过的，故考虑优化。

每次查询区间是一定的，所以就维护一个变量 $sum$ 表示 $1→n$ 的和，再推平时统计，推平区间里有多少个元素值会变化，再根据变成什么修改 $sum$

```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;

#define int long long
int sum;

// 柯朵莉树模板
struct Node {
    int l, r;      // l和r表示这一段的起点和终点
    mutable int v; // v表示这一段上所有元素相同的值是多少,注意关键字 mutable,使得set中结构体属性可修改
    bool operator<(const Node &b) const {
        return l < b.l; // 规定按照每段的左端点排序
    }
};
set<Node> s; // 柯朵莉树的区间集合

// 分裂:[l,x-1],[x,r]
set<Node>::iterator split(int x) {
    auto it = s.lower_bound({x});
    if (it != s.end() && it->l == x) return it; // 一击命中
    it--;                                       // 没有找到就减1个继续找
    if (it->r < x) return s.end();              // 真的没找到,返回s.end()

    int l = it->l, r = it->r, v = it->v; // 没有被返回，说明找到了,记录下来，防止后面删除时被破坏
    s.erase(it);                         // 删除整个区间
    s.insert({l, x - 1, v});             //[l,x-1]拆分
    // insert函数返回pair，其中的first是新插入结点的迭代器
    return s.insert({x, r, v}).first; //[x,r]拆分
}

// 区间加
void add(int l, int r, int v) {
    // 必须先计算itr,后计算itl
    auto R = split(r + 1), L = split(l);
    for (auto it = L; it != R; it++) it->v += v;
}
// 区间赋值
void assign(int l, int r, int v) {
    auto R = split(r + 1), L = split(l);

    // 趁着没删除掉，赶快计算
    int res = 0;
    for (auto it = L; it != R; it++)
        if (it->v != v) res += it->r - it->l + 1; // 一共有多少值会变

    s.erase(L, R);       // 按迭代器开始删除中部的所有块
    s.insert({l, r, v}); // 插入新构建的整个的块

    sum += ((v == 0) ? -res : res); // 是加还是减
}
int n, q;

signed main() {
#ifndef ONLINE_JUDGE
    freopen("CF915E.in", "r", stdin);
#endif
    cin >> n >> q;
    // 柯朵莉树插入最初始的块，值为1
    s.insert({1, n, 1});

    sum = n;
    while (q--) {
        int l, r;
        cin >> l >> r;
        int op;
        cin >> op;
        if (op == 1) {
            assign(l, r, 0);
            printf("%lld\n", sum);
        } else {
            assign(l, r, 1);
            printf("%lld\n", sum);
        }
    }
    return 0;
}
```