专栏文章

题解：AT_abc392_f [ABC392F] Insert

kksmgxeh
AT_abc392_f题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miq94e32
此快照首次捕获于
2025/12/04 00:58
3 个月前
此快照最后确认于
2025/12/04 00:58
3 个月前
查看原文
赛时看到这道题题面马上想到了另一道很相近的题目：P10497。
因为我们从后往前看，最后一个数的位置一定是确定的，即一定处于 PnP_n 位置。所以不难想到从后往前进行操作，这样每个数的位置都能被唯一确定。
具体实现也很简单，用树状数组维护每个数前面有多少个位置已经被占用，查询时用二分即能确定当前数的位置。
时间复杂度 O(nlog⁡n)O(n\log n)，可以通过。
CPP
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5+5;
int n,p[N],c[N],a[N];

void add(int x,int k){
	for(int i=x;i<=n;i+=i&-i) c[i]+=k;
}
int get(int x){
	int res=0;
	for(int i=x;i;i-=i&-i) res+=c[i];
	return res;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) add(i,1);
    for(int i=n;i>=1;i--){
    	int l=1,r=n;
    	while(l<r){
    		int mid=l+r>>1;
    		if(get(mid)>=p[i]) r=mid;
    		else l=mid+1;
		} a[l]=i,add(l,-1);
	}
	for(int i=1;i<=n;i++) cout<<a[i]<<' ';
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...