[Codeforces 1208D]Restore Permutation (树状数组)

题面

有一个长度为n的排列a。对于每个元素i，\(s_i\)表示\(\sum_{j=1,a_j<a_i}^i a_j\).即前面比它小的元素的值之和。

给出\(s_1,s_2 \dots s_n\),求a

分析

考虑如何求\(a_n\),\(s_n\)实际上表示的是1~n中比\(a_n\)小的所有数的和，可以直接求出\(a_n\)

然后我们可以倒序求\(a_i\)，求到\(a_i\)的时候，我们已经知道\(a_i\)前面有哪些数，只是不知道顺序。维护一个数据结构存储这些数的集合，并存储从小到大排列后的前缀和，然后二分出最后一个前缀和\(\leq s_i\)的位置。

比如最后一个样例：

input:

5

0 1 1 1 10

output:

1 4 3 2 5

我们求到第4个数的时候，由于第5个数已经求出来是5，那前面的数就是{1,2,3,4}，2之前的前缀和是1，1之前的前缀和是0，那么二分出的点就是2.

具体实现可以用树状数组，初始时候给第i个位置加i，求出某个数的值为x之后把第x个位置-x,相当于把x移出集合

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

#define maxn 200000

using namespace std;

typedef long long ll;

int n;

struct fenwick_tree{

	ll c[maxn+5];

	inline int lowbit(int x){

		return x&(-x);

	}

	inline void update(int x,int v){

		for(int i=x;i<=n;i+=lowbit(i)){

			c[i]+=v;

		}

	}

	inline ll query(int x){

		ll ans=0;

		for(int i=x;i>0;i-=lowbit(i)) ans+=c[i];

		return ans;

	}

}T;

ll a[maxn+5];

int ans[maxn+5];

int bin_search(int l,int r,ll sum){

	int ans=n;

	int mid;

	while(l<=r){

		mid=(l+r)>>1;

		if(T.query(mid-1)<=sum){

			ans=mid;

			l=mid+1;

		}else r=mid-1;

	}

	return ans;

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++){

		scanf("%I64d",&a[i]);

	}

	for(int i=1;i<=n;i++) T.update(i,i);

	for(int i=n;i>=1;i--){

		int k=bin_search(1,n,a[i]);

		ans[i]=k;

		T.update(k,-k);

	}

	for(int i=1;i<=n;i++) printf("%d ",ans[i]);

}