HDU 3577 Fast Arrangement [线段树+区间修改+维护最大值]

\(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\)

三、实现代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

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

struct Node {
    int l, r;
    int sum; //记录的区间中车上人数
    int tag; // 延迟标记
} tr[N << 2];

int res[N]; //用来存结果

/**
 * @brief 更新父节点信息
 *
 * @param u
 */
void pushup(int u) {
    tr[u].sum = max(tr[u << 1].sum, tr[u << 1 | 1].sum);
}

/**
 * @brief 推送懒标记
 *
 * @param u
 */
void pushdown(int u) {
    Node &root = tr[u], &ls = tr[u << 1], &rs = tr[u << 1 | 1];
    if (root.tag) {
        tr[u << 1].tag += tr[u].tag, tr[u << 1].sum += tr[u].tag;
        tr[u << 1 | 1].tag += tr[u].tag, tr[u << 1 | 1].sum += tr[u].tag;
        tr[u].tag = 0; //清空懒标记
    }
}

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

void modify(int u, int l, int r, int d) {
    if (l <= tr[u].l && r >= tr[u].r)
        tr[u].tag += d, tr[u].sum += d;
    else {
        //向下推送懒标记
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, d);
        if (r > mid) modify(u << 1 | 1, l, r, d);

        //子节点信息修改了，需要向上推送信息
        pushup(u);
    }
}
/**
 * @brief 查询区间人数
 *
 * @param u
 * @param l
 * @param r
 * @return int
 */
int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum; //完全区间命中
    
    //分裂
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid)
        return query(u << 1, l, r);
    else if (l > mid)
        return query(u << 1 | 1, l, r);
    else
        return max(query(u << 1, l, r), query(u << 1 | 1, l, r));
}

int main() {
    //加快读入
    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, 1000000); //后面这个1e6用的漂亮

        int idx = 0;
        for (int i = 1; i <= q; i++) {
            cin >> a >> b;
            if (query(1, a, b - 1) < k) { // a上车，b下车，b位置可以售卖，[a,b)
                modify(1, a, b - 1, 1);
                res[idx++] = i;
            }
        }
        printf("Case %d:\n", ++cas);

        //注意格式输出
        for (int i = 0; i < idx - 1; i++) printf("%d ", res[i]);
        printf("%d \n\n", res[idx - 1]);
    }
    return 0;
}