POJ 2828 Buy Tickets

题目传送门

一、题目大意

有很多人排队，其中有插队的，每个人都有一个值。现在给出这些人排队插队的位置以及他们的值，要求输出最后形成的队列。

二、解题思路

每一次插队就像线段树里面的单点更新，只不过需要考虑插入位置。
插队的肯定在被插队的前面并且最后插队的人的位置是不变的，所以建一颗树来维护当前区间空位，
然后倒着考虑进行单点更新从最后一个插队到第一个在这里排队的人，这样每一次插入都会在插队后面，
最后形成整个队列。

三、实现代码

//线段树二分模板
//#include 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
const int N = 200010;
typedef pair PII;

int n, res[N];

struct Node {
    int l, r;
    int sum; //此区间内空位置的数量
} tr[N << 2];

PII a[N];

void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r) {
    tr[u] = {l, r};
    if (l == r) {
        tr[u].sum = 1; //每个叶子节点初始化为1
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u); //叶子有初始值1，所以这里需要向上更新信息
}

void modify(int u, int k, int v) {
    if (tr[u].l == tr[u].r) {
        tr[u].sum = 0;    //修改已有人占用，无法再次使用
        res[tr[u].l] = v; //用结果数组记录最后此位置上是v这个编号的人员
        return;
    }
    //如果修改的位置在左侧，那么直接修改左侧第k个信息
    if (k <= tr[u << 1].sum)
        modify(u << 1, k, v);
    else //如果在右侧，修改右侧第 x 减去 可以数量后位置的信息
        modify(u << 1 | 1, k - tr[u << 1].sum, v);

    //更新父节点信息
    pushup(u);
}
int main() {
    while (scanf("%d", &n) != EOF) {
        build(1, 1, n); //构建一个叶子节点值为1的线段树，描述此区间内空位置的数量

        for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].first, &a[i].second);

        //正难则反，看把好确定的确定下来，那就是n,n-1,n-2,...
        for (int i = n; i; i--) modify(1, a[i].first + 1, a[i].second);

        //输出结果
        for (int i = 1; i <= n; i++) cout << res[i] << ' ';
        puts("");
    }
    return 0;
}
AcWing提高课

相关

标签