题目大意
给你一个序列s
让你求一个1~n的序列
使得对于第i个位置它前面所有小于p[i]的数的和恰好为s[i]
分析
我们可以从后往前确定每一位
每次一二分找到恰好等于s[i]的数
但是我们发现这样会产生重复选一个点的情况
所以我们改为每次找第一个大于s[i]的点
这个点-1恰好为答案
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define int long long
int d[200100],n,s[200100],a[200100];
inline int lb(int x){return x&(-x);}
inline void add(int x,int k){while(x<=n)d[x]+=k,x+=lb(x);}
inline int q(int x){int res=0;while(x)res+=d[x],x-=lb(x);return res;}
signed main(){
int i,j,k;
scanf("%lld",&n);
for(i=1;i<=n;i++)scanf("%lld",&s[i]);
for(i=1;i<=n;i++)add(i,i);
for(i=n;i>0;i--){
int le=0,ri=n,ans;
while(ri-le>1){
int mid=(le+ri)>>1;
if(q(mid)<=s[i])le=mid;
else ri=mid;
}
a[i]=ri;
add(a[i],-a[i]);
}
for(i=1;i<=n;i++)printf("%lld ",a[i]);
puts("");
return 0;
}