python/TangDou/AcWing/SegmentTree/HDU3577.cpp

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