Solution #

Let the input be $A$ and the answer be $P$ . $A_i-A_{i-1}$ is the number of numbers that are greater than $P_i$ , so we can also know the how many numbers are smaller than $P_i$ . Now we build a segment tree which counts the occurrence of numbers in $1\dots n$ and iterate $A$ reversely, we could know how many unused numbers are smaller than $P_i$ and then find the corresponding number in the segtree and decrease the occurrence of that number by one.

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;
}

Solution for HDU 5592 - ZYB's Premutation

Solution #

Code #