【POJ】2828 Buy Tickets 题解

题目大意

有 $n$ 个人前来排队，第 $i$ 个人编号为 $val[i]$，来了之后会站在队伍中第 $p[i]$ 个人后面，问最后的队伍是什么样子的。

题目链接

思路

我们注意到，每次有新来的人来插队，他只会影响到已经在队伍中的人的占位，而之前的人的占位不会影响后面的人的占位。

而对已经在队伍中的人做修改，时间复杂度较高，我们不妨反着考虑。从最后一个人开始，往前考虑。此时对于每个人的位置，我们只需要看有多少个人站在了它前面。

这样我们就从修改多个人的位置，变成了维护后来的人对前面的人的影响。从”一对多”，变成了”多对一”。而我们有很多种算法来解决这种问题。

那么第 $n$ 个人的占位就是 $p[i] + 1$，接下来考虑第 $p[n-1]$，如果：

• $p[n] > p[n-1]$，即第 $n$ 站在了第 $n-1$ 个人的后面，那么 $ans[n-1] = p[n-1] + 1$。
• $p[n] \le p[n-1]$，即第 $n$ 站在了第 $n-1$ 个人的前面，那么 $ans[n-1] = p[n-1] + 2$。

所以我们的任务就是计算第 $i$ 个人前面站了多少人，再加上 $p[i] + 1$ 就是最终答案。

那么其实就是相当于寻找第 $p[i] + 1$ 个空余的位置。

因为它的最终位置就是 $p[i] + 1 + cnt$（前面人的数量），那么就说明前面有 $cnt$ 个位置被占用了，减掉 $cnt$，就得出了它前面有 $p[i]$ 个空余位置。

代码

#include <cstdio>
#include <iostream>
using namespace std;

const int maxN = 2e5 + 7;

int n, ans[maxN], a[maxN], val[maxN];

struct Tree{
    int l, r, sum;
}t[maxN << 2];

void build(int l, int r, int num)
{
    t[num].l = l; t[num].r = r;
    if(l == r) {
        t[num].sum = 1;
        return ;
    }
    int mid = (l + r) >> 1;
    build(l, mid, num << 1);
    build(mid + 1, r, num << 1 | 1);
    t[num].sum = t[num << 1].sum + t[num << 1 | 1].sum;
}

void change(int num, int pos, int x, int val) // 寻找第x个空余位置，并修改，然后记录答案
{
    if(t[num].l == t[num].r) {
        t[num].sum += x;
        ans[t[num].l] = val;
        return ;
    }
    int mid = (t[num].l + t[num].r) >> 1;
    if(pos <= t[num << 1].sum)
        change(num << 1, pos, x, val);
    else 
        change(num << 1 | 1, pos - t[num << 1].sum, x, val);
    t[num].sum = t[num << 1].sum + t[num << 1 | 1].sum;
}

int main()
{
    while(~scanf("%d", &n)) {
        build(1, n, 1);
        for(int i = 1; i <= n; ++i) 
            scanf("%d%d", &a[i], &val[i]);
        for(int i = n; i >= 1; --i)
            change(1, a[i] + 1, -1, val[i]);
        for(int i = 1; i <= n; ++i)
            printf("%d ", ans[i]);
        printf("\n");
    }
    return 0;
}