python/TangDou/AcWing/SegmentTree/HDU3577.md

##[$HDU$ $3577$ $Fast$ $Arrangement$](http://acm.hdu.edu.cn/showproblem.php?pid=3577)

### 一、题目解析
由于中国庞大的人口和站台，总是出现票的问题，现在政府需要你去开发一个新的查票系统。

一个火车只能载$k$个乘客，并且每个乘客仅仅只能从$a->b$买一张票，在任何时间每辆火车载客不超过$k$人，一个人提前买的票将是有效的。

需要注意的是这个人在$b$点下车了，座位就空出来了，可以卖给下一个人，即每个区间是$[a,b)$


**输入**：

多组测试数据，第一行测试组数，接下来每组的第一行，为$k$（列车的承载人数），$Q$（几组数据）；接下来$Q$行，每行有两个数字$a$和$b$

**输出**：

每组测试数据输出三行，第一行测试组数，如果第$i$次查询满足题意输出从$1$到$i$，每个数字有一个空格，每组测试后有一个空行

**测试用例**
```cpp {.line-numbers}
1
3 6
1 6
1 6
3 4
1 5
1 2
2 4
```

**输出**
```cpp {.line-numbers}
Case 1:
1 2 3 5 
```

**解释样例**：
`1 6`: 从$1$上车，到$6$下车,此时$1\sim 5$存在$1$人
`1 6`: 从$1$上车，到$6$下车,此时$1\sim 5$存在$2$人
`3 4`: 从$3$上车，到$4$下车,此时$1 \sim 2$两人，$3$存在最大人数$3$人,$4 \sim 5$存在$2$人
`1 5`: 从$1$上车，到$5$下车,此时遇到问题，$3$站点已经$3$人，再卖给$1 \sim 5$就冲突了，**失败**
`1 2`: 从$1$上车，到$2$下车,此时$1$是$3$人,$2$是两人，没有问题
`2 4`: 从$2$上车，到$4$下车,此时$3$站点存在问题，**失败**

综上，可以售卖的是$1\sim 2 \sim 3 \sim 5$

### 二、经验总结

#### 性质
<font color='red' size=4><b>区间维护最大值、最小值，如果区间整体加了一个值$v$,最大值、最小值也需要加$v$。</b></font>

- 本题就是区间全部加上一个$1$,然后由线段树记录、查询出指定区间内的最大值即可。

- 同时需要注意的是开闭区间的处理，开区间，也就是不包括的那个点，不进行计算即可。

#### 懒标记的叠加
懒标记的使用可以大大提高线段树的效率，特别是在处理范围更新操作时。对于某些操作，懒标记可以叠加使用，即多个操作可以同时存在于同一个节点上，而不必立即执行。

这种叠加的原因是因为某些操作具有可累加性质。比如，在线段树中使用懒标记进行区间加法操作，假设有两个区间 $[l1, r1]$ 和 $[l2, r2]$，且它们满足 $l2 > r1$，则这两个区间的加法操作可以叠加在同一个节点上，只需要记录增加的值即可。当查询某个位置时，需要将懒标记叠加的值依次累加到查询结果中。

值得注意的是，并不是所有的操作都可以叠加使用懒标记。一些操作，比如区间赋值操作，就不适合叠加懒标记，因为这些操作会直接覆盖原有的值，而不是进行简单的加法或乘法等运算。在使用懒标记的时候，需要根据具体的操作和需求来确定是否可以叠加使用懒标记。

### 三、实现代码
```cpp {.line-numbers}
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;
const int N = 1e6 + 10;

// 线段树模板
struct Node {
    int l, r;
    int mx;  // 区间人数最大值
    int tag; // 懒标记
} tr[N << 2];

void pushup(int u) {
    tr[u].mx = max(tr[u << 1].mx, tr[u << 1 | 1].mx); // 向上更新区间最大值
}

void pushdown(int u) {
    if (tr[u].tag) {                                                     // 如果u节点有懒标记
        tr[u << 1].tag += tr[u].tag, tr[u << 1].mx += tr[u].tag;         // 将懒标记下传给左儿子，并且，区间整体加上一个数，意味着区间最大值也加上了这个数
        tr[u << 1 | 1].tag += tr[u].tag, tr[u << 1 | 1].mx += tr[u].tag; // 同上
        tr[u].tag = 0;                                                   // 清除u节点懒标记
    }
}

void build(int u, int l, int r) {
    tr[u] = {l, r};
    if (l == r) return; // 这里与前一个题不同，不需要初始值1，因为表示默认没有人在这个区间坐车

    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    // 此题因为只是构建一个空的线段树，不需要更新父节点信息
    // 当然，为了和背的模板一样，也可以无脑的写上pushup(u);
    pushup(u);
}

// 区间[l,r]统一增加v
void modify(int u, int l, int r, int v) {
    if (l <= tr[u].l && r >= tr[u].r) {
        tr[u].tag += v; // 懒标记 (什么时候懒标记可以叠加，什么时候不可以呢？)
        tr[u].mx += v;  // 区间人数最大值也需要加上v
        return;
    }
    // 下放懒标记
    pushdown(u);
    // 分裂
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid) modify(u << 1, l, r, v);    // 与左区间有交集
    if (r > mid) modify(u << 1 | 1, l, r, v); // 与右区间有交集
    pushup(u);                                // 将结果的变更更新到祖先节点
}

int query(int u, int l, int r) {
    if (l > tr[u].r || r < tr[u].l) return 0;          // 递归出口，不在我管辖范围内的情况，返回0
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].mx; // 完整区间覆盖，返回区间和

    // 下放懒标记
    pushdown(u);
    // 分裂
    int mid = (tr[u].l + tr[u].r) >> 1;
    int mx = 0;
    if (l <= mid) mx = query(u << 1, l, r);             // 与左子区间有交集
    if (r > mid) mx = max(mx, query(u << 1 | 1, l, r)); // 与右子区间有交集
    return mx;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("HDU3577.in", "r", stdin);
#endif
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    int k, q;
    int a, b;
    cin >> T;
    int cas = 0;
    while (T--) {
        cin >> k >> q;

        // 构建线段树
        build(1, 1, N); // 学会上限的处理技巧

        vector<int> res;
        for (int i = 1; i <= q; i++) {
            cin >> a >> b;
            // a上车，b下车，b位置可以售卖，[a,b)
            // 总结：这玩意开区间的位置不在讨论范围内啊，不用处理就OK啊~
            // 准备在区间[a,b)售票，区间的最大值是k-1,保证在区间内不超过k
            if (query(1, a, b - 1) < k) {
                // 对于线段树的[a,b)=[a,b-1]整体区间+1
                modify(1, a, b - 1, 1);
                // 记录第i次操作是成功的操作
                res.push_back(i);
            }
        }
        printf("Case %d:\n", ++cas);

        // 注意格式输出
        for (auto c : res) printf("%d ", c);
        printf("\n\n");
    }
    return 0;
}
```