D. Restore Permutation

D. Restore Permutation

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output

An array of integers p1,p2,…,pn is called a permutation if it contains each number from 1 to n exactly once. For example, the following arrays are permutations: [3,1,2],[1],[1,2,3,4,5] and [4,3,1,2]. The following arrays are not permutations: [2],[1,1],[2,3,4].

There is a hidden permutation of length n.

For each index i, you are given si, which equals to the sum of all pj such that j<i and pj<pi. In other words, si is the sum of elements before the i-th element that are smaller than the i-th element.

Your task is to restore the permutation.

Input
The first line contains a single integer n (1≤n≤2⋅105) — the size of the permutation.

The second line contains n integers s1,s2,…,sn (0≤si≤n(n−1)2).

It is guaranteed that the array s corresponds to a valid permutation of length n.

Output
Print n integers p1,p2,…,pn — the elements of the restored permutation. We can show that the answer is always unique.

Examples
inputCopy
3
0 0 0
outputCopy
3 2 1
inputCopy
2
0 1
outputCopy
1 2
inputCopy
5
0 1 1 1 10
outputCopy
1 4 3 2 5
Note
In the first example for each i there is no index j satisfying both conditions, hence si are always 0.

In the second example for i=2 it happens that j=1 satisfies the conditions, so s2=p1.

In the third example for i=2,3,4 only j=1 satisfies the conditions, so s2=s3=s4=1. For i=5 all j=1,2,3,4 are possible, so s5=p1+p2+p3+p4=10.

对于这种序列，我们可以考虑从 1 -> n 去构造答案，我们可以试想对于1来说，肯定是最后一个0的位置对不对，然后我们可以让0后面的所有数字就减去1，这样继续找0最后的位置即可。然后对于找到的位置后面所有元素减少 i ，同时我们要注意让当前找到的位置删掉，就是直接赋值为INF即可（当时sb了，赋值为99999999.。。。。1e18就AC了）。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,cnt,res[N];
struct node{
	int l,r,mi,add;
}t[N<<2];
inline void push_up(int p){
	t[p].mi=min(t[p<<1].mi,t[p<<1|1].mi);
}
inline void push_down(int p){
	if(t[p].add){
		t[p<<1].mi-=t[p].add;	t[p<<1|1].mi-=t[p].add;
		t[p<<1].add+=t[p].add;	t[p<<1|1].add+=t[p].add;
		t[p].add=0;
	}
}
void build(int p,int l,int r){
	t[p].l=l; t[p].r=r;
	if(l==r){
		scanf("%lld",&t[p].mi);	return ;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);	build(p<<1|1,mid+1,r);
	push_up(p);
}
void change(int p,int l,int r,int v){
	if(t[p].l==l&&t[p].r==r){
		t[p].mi-=v;	t[p].add+=v;	return ;
	}
	push_down(p);
	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	change(p<<1,l,r,v);
	else if(l>mid)	change(p<<1|1,l,r,v);
	else	change(p<<1,l,mid,v),change(p<<1|1,mid+1,r,v);
	push_up(p);
}
void updata(int p,int x){
	if(t[p].l==t[p].r){
		t[p].mi=1e18;	return ;
	}
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid)	updata(p<<1,x);
	else	updata(p<<1|1,x);
	push_up(p);
}
int ask(int p,int x){
	if(t[p].l==t[p].r)	return t[p].l;
	int mid=t[p].l+t[p].r>>1;	push_down(p);
	if(t[p<<1|1].mi<=x)	return ask(p<<1|1,x);
	else	return ask(p<<1,x);
}
signed main(){
	cin>>n;	build(1,1,n);
	for(int i=1;i<=n;i++){
		int x=ask(1,0);	res[x]=i;	updata(1,x);
		if(x!=n)	change(1,x+1,n,i);
	}
	for(int i=1;i<=n;i++)	cout<<res[i]<<' ';puts("");
	return 0;
}