python/TangDou/AcWing/SegmentTree/HDU3577.md

##HDU 3577 Fast Arrangement

一、题目解析

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

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

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

输入：

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

输出：

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

测试用例

1
3 6
1 6
1 6
3 4
1 5
1 2
2 4

输出

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

二、经验总结

性质

区间维护最大值、最小值，如果区间整体加了一个值v,最大值、最小值也需要加v。

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

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

懒标记的叠加

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

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

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

三、实现代码

#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;
}