[推销博客](https://foreverlasting1202.github.io/2019/08/27/CF1208%E9%A2%98%E8%A7%A3/)
### D Restore Permutation
题意:未知一个长度为$n$的排列,对于位置$i$,假设在上面的数是$a_i$,给出$\sum_{j<i,a_j<a_i} a_j$,求这个排列。$1\leq n\leq 2\ast 10^5$。
做法:从后往前递推,显然最后一个未知的都可以二分出来,只需要动态维护前缀和,树状数组即可。复杂度$O(nlog^2n)$。
code:
```cpp
//2019.8.24 by ljz
//email
[email protected]
//if you find any bug in my code
//please tell me
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f
#define unl __int128
#define eps 5.6e-8
#define RG register
#define db double
#define pc(x) __builtin_popcount(x)
typedef pair<int,int> Pair;
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pb push_back
#define ull unsigned LL
#define gc getchar
//inline char gc() {
// static char buf[100000],*p1,*p2;
// return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
inline int read() {
res s=0,ch=gc();
while(ch<'0'||ch>'9')ch=gc();
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
return s;
}
//inline int read() {
// res s=0,ch=gc(),w=1;
// while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
// while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
// return s*w;
//}
inline LL Read() {
RG LL s=0;
res ch=gc();
while(ch<'0'||ch>'9')ch=gc();
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
return s;
}
//inline LL Read() {
// RG LL s=0;
// res ch=gc(),w=1;
// while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
// while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
// return s*w;
//}
//inline void write(RG unl x){
// if(x>10)write(x/10);
// putchar(int(x%10)+'0');
//}
inline void swap(res &x,res &y) {
x^=y^=x^=y;
}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//clock_t start=clock();
//inline void ck(){
// if(1.0*(clock()-start)/CLOCKS_PER_SEC>0.1)exit(0);
//}
const int N=2e5+10;
namespace MAIN{
int n;
#define lowbit(x) (x&-x)
LL tr[N];
LL a[N];
inline void modify(const res &x,const res &y){
for(res i=x;i<=n;i+=lowbit(i))tr[i]+=y;
}
inline LL query(const res &x){
RG LL ret=0;
for(res i=x;i;i-=lowbit(i))ret+=tr[i];
return ret;
}
int A[N];
inline void MAIN(){
// printf("%d\n",0^2^4^11);
// printf("%d\n",19^55^11^39^32^36^4^52);
n=read();
for(res i=1;i<=n;i++)a[i]=Read(),modify(i,i);
for(res i=n;i;i--){
res l=1,r=n,ret=0;
while(l<=r){
res mid=(l+r)>>1;
if(query(mid-1)<=a[i])l=mid+1,ret=mid;
else r=mid-1;
}
A[i]=ret;
modify(ret,-ret);
}
for(res i=1;i<=n;i++)printf("%d ",A[i]);
}
}
int main(){
// srand(19260817);
// freopen("signin.in","r",stdin);
// freopen("signin.out","w",stdout);
MAIN::MAIN();
return 0;
}
```