题解：P10497 【重题】
MoCaRabbit
·
·
题解
呃啊，怎么改题了。
于是我，又过来了。
因为改题后也很简单。
题意是这样的：
有 n 个数组成的数列，已知它们每个数前面有多少个比它小的数。
求每个数的排名。
设已知的大小数列为 a，排名数列为 rk。
从后向前考虑，因为 rk_n 就等于 a_n+1。
这个很好想。
因为前 n-1 个数加它本身就是整个数列。
接着，推不动了。
即使知道了 rk_n 也无法推算 rk_{n-1}。
于是，辅助数组，启动。
可以设置一个 bool 型的辅助数组 f 。
计算出 $rk_n$ 可以更新 $f$ 数组。
然后，就在剩下的 $n-1$ 个 $1$ 中选择。
这 $n-1$ 个 $1$ 代表前 $n-1$ 个没选的。
第 $n-1$ 个数是前 $n-1$ 个数的第 $a_{n-1}+1$ 小。
所以，在现存 $f$ 数组上，选择正数第 $k$ 个 $1$ 的那个位子（下标），就是 $rk_{n-1}$。
然后，修改 $f$ 数组，依此类推。
梳理一下，我们需要（对 $f$ 数组）干什么。
第一，单点修改。
第二，查询前缀和为 $k$ 的位置。
仅此而已。
单点加前缀，可以启动树状数组。
查询位置，启动二分。
时间复杂度 $O(n\log^2n)$。
不够优秀。
因为树状数组是倍增思想的产物，所以果断选择用倍增替换二分。
每次倍增，我们需要求区间 $[2^a+2^b\dots2^n+1,2^a+2^b\dots2^n+2^m]$ 的值。
等一下,这个值不是树状数组 $c_{2^a+2^b\dots2^n+2^m}$ 的值吗？
赚大了。
第 $k$ 小，时复降低到 $O(\log n)$ 了（倍增的时间）。
时间复杂度 $O(n\log n)$。
代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010];
int c[100010];
inline int lowbit(int x){
return x&-x;
}
inline void update(int x,int k){
while(x<=n) c[x]+=k,x+=lowbit(x);
}
inline int get_kth(int k){
int ans=0,sum=0;
for(int i=30;i>=0;i--){
if(ans+(1<<i)>n) continue;
if(sum+c[ans+(1<<i)]<k) ans+=(1<<i),sum+=c[ans];
}
return ans+1;
}
int ans[100010];
int main() {
ios::sync_with_stdio(0);
cin>>n;
update(1,1);
for(int i=2;i<=n;i++) cin>>a[i],update(i,1);
for(int i=n;i>=1;i--){
int p=get_kth(a[i]+1);
update(p,-1);
ans[i]=p;
}
for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
return 0;
}
```