Thallium54

HDU 5592 - ZYB's Premutation 题解

数据结构 线段树 题解

妙啊

Problem Link

题解 #

我们用AA表示输入，用PP表示答案。Ai−Ai−1A_i-A_{i-1}就是比PiP_i大的数字的个数因此我们也能知道比PiP_i小的数的个数。我们可以用权值线段树然后从后遍历AA，这样我们就能得到所有没用过的比PiP_i小的数的个数，然后在线段树中找到对应的数并更新线段树。

Code #

#include <bits/stdc++.h>
 
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
using namespace std;
 
const int N=5e4+5;
int sum[N<<2];
void build(int k,int l,int r){
	sum[k]=r-l+1;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}
int query(int root,int l,int r,int p){
	sum[root]--;
	if(l==r) return l;
	int mid=(l+r)>>1;
	if(sum[root<<1]>=p) return query(root<<1,l,mid,p);
	else return query(root<<1|1,mid+1,r,p-sum[root<<1]);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int tt;
	cin>>tt;
	while(tt--){
		int n;
		cin>>n;
		vector<int> a(n+1),ans(n+1);
		for1(i,n) cin>>a[i];
		build(1,1,n);
		for(int i=n;i>0;i--){
			int p=a[i]-a[i-1];
			p=i-p;
			ans[i]=query(1,1,n,p);
		}
		for1(i,n) cout<<ans[i]<<(i==n?'\n':' ');
	}
    return 0;
}