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

题目传送门

一、题目解析

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

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

输入：

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

输出：

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

解释样例：
\(1-> 6\) 已经占了两个座位，\(3->4\)在\(3\)站台可以上车，\(1->5\)由于\(3->4\)经过的站与其有重复并且\(3->4\)先买的票，所以\(1->5\)不满足条件，\(1->2\)由于之前只有两个\(1->6\)经过\(1->2\)站，所以刚好可以坐上车，\(2->4\)与\(1->5\)同理，因为与\(3->4\)有重复。所以第\(1，2，3，5\)个乘客满足条件。

二、经验总结

  • 区间维护最大值、最小值，如果整个区间加了一个值\(v\),其实最大值、最小值也是加了一个\(v\)
  • https://www.bilibili.com/video/BV1Tk4y1m7VM?p=6 讲解了这部分的知识

三、实现代码

//#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

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

struct Node {
    int l, r;
    int sum; //记录的区间中车上人数
    int add; // 延迟标记
} 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) {
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add) {
        tr[u << 1].add += tr[u].add, tr[u << 1].sum += tr[u].add;
        tr[u << 1 | 1].add += tr[u].add, tr[u << 1 | 1].sum += tr[u].add;
        tr[u].add = 0; //清空懒标记
    }
}

/**
 * @brief 构建线段树，此时为一个空的线段树，没有进行初始化
 *
 * @param u
 * @param l
 * @param r
 */
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);
}

void modify(int u, int l, int r) {
    if (l <= tr[u].l && r >= tr[u].r) {
        tr[u].add += 1, tr[u].sum += 1;
        return;
    }
    //向下推送懒标记
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify(u << 1, l, r);
    if (r > mid) modify(u << 1 | 1, l, r);
    //子节点信息修改了，需要向上推送信息
    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() {
    int T;
    int k, q;
    int a, b;
    scanf("%d", &T);
    int cas = 0;
    while (T--) {
        scanf("%d%d", &k, &q);

        build(1, 1, 1000000);

        int idx = 0;
        for (int i = 1; i <= q; i++) {
            scanf("%d%d", &a, &b);
            if (query(1, a, b - 1) < k) {
                modify(1, a, b - 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;
}
线段树HDU

相关

「acmhdu - 6314」Matrix

#直径，线段树#51nod 1766 树上的最远点对

「NOI2020」命运（树形DP+线段树合并）

HDU-5885 XM Reserves (FFT)

线段树学习笔记 1

HDU 2457 POJ 3691 DNA repair（AC自动机+DP）

HDU 2825 Wireless Password（AC自动机+DP）

关于 线段树 的一些认识

2020 hdu contest1 水题

HDU - 1754 I Hate It

HDU 3038 - How Many Answers Are Wrong

线段树

标签