POJ2828

题目大意

有\(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] <> 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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/04/28/POJ2828/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！