自动搬运

查看原文

来自洛谷，原作者为

	qcf2010 如履薄冰 || 一心只想拿蓝勾

搬运于2025-08-24 23:00:17，当前版本为作者最后更新于2025-08-18 15:33:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识

• 树状数组
• 二分

思路

如果按照正常顺序从前向后模拟，问题会变得很复杂。但是反过来，我们从最后一个人开始从后向前模拟，整个问题就会变得非常简单。

为什么呢？考虑一个简单的例子：首先来了一个人，站在第 $1$ 个人后面。接着又来了若干个人，都没有素质插在第 $1$ 个人的后面。最后一个人来了，他也没有素质插在了第 $1$ 个人后面。诶，此时，最后一个人就是第 $1$ 个人后面的第一个人。

发现了什么？最后一个插队的人是离他所排的人最近的，而第一个插队的人是离他所排的人最远的。

所以，从后往前模拟，就可以顺利解决此题。扫描每一个人，若他排在第 $x$ 个人后面，那么查找队伍中哪一个位置前面有 $x$ 个空位，然后把这个人放在这里。

如何快速获取从队头到某一处之间有多少个空位？使用树状数组，维护每一个位置上有没有人（有人为 $0$，没人为 $1$）。利用树状数组能快速求出区间和的性质，即可求出从队头到某一处之间有多少个空位。那如何查找到这个位置？很自然地可以想到二分查找。

至此，问题解决。

代码

#include<bits/stdc++.h>
using namespace std;

int n;
int a[200010],v[200010];
int ans[200010];

int c[200010];

void Add(int x,int y){
	for(;x<=n;x+=x&-x) c[x]+=y;
}

int Query(int x){
	int ans=0;
	for(;x;x-=x&-x) ans+=c[x];
	return ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	while(cin>>n){
		for(int i=1;i<=n;++i) c[i]=0;
		for(int i=1;i<=n;++i) Add(i,1);
		for(int i=1;i<=n;++i) cin>>a[i]>>v[i];
		for(int i=n;i>=1;--i){
			int l=1,r=n;
			while(l<r){
				int mid=(l+r)>>1;
				if(Query(mid)>=a[i]+1) r=mid;
				else l=mid+1;
			}
			ans[l]=v[i];
			Add(l,-1);
		}
		for(int i=1;i<=n;++i) cout<<ans[i]<<" ";
		cout<<"\n";
	}

	return 0;
}