其实应该叫倍增。
由于这篇文章中 \(\text{lowbit}\)
Acwing244. 谜一样的牛
给定一个长度 \(n\le 10^5\) 序列，求逆康托。
\(0\le a_i<i\)
若是 \(\log n\) 二分，再 \(\log n\) Fenwick，\(O(n\log^2 n)\) 要跑 600ms，数据加强一下就过不了。
若是 \(\log n\) 在线段树上二分，常数过大。
所以我们就请出了主题——树状数组上二分
原理是位置 \(x\) 存的是以 \(x\) 为右端点长度为 \(\text{low}\)
/*
* Author: ShaoJia
* Last Modified time: 2022-09-26 19:47:51
* Motto: We'll be counting stars.
*/
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define For(i,j,k) for(int i=(j),i##_=(k);i<=i##_;i++)
#define Rof(i,j,k) for(int i=(j),i##_=(k);i>=i##_;i--)
const int N=1e5+5;
int n,a[N],c[N],b[N];
inline int low(int x){ return x&(-x); }
void add(int x,int y){ while(x<=n) c[x]+=y,x+=low(x); }
int jump(int x){//the last pos that presum<=x
int pos=0,sum=0,np;
Rof(i,20,0)
if((np=pos|(1<<i))<=n && sum+c[np]<=x)
sum+=c[np],pos=np;
return pos;
}
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);
cin>>n;
For(i,2,n) cin>>a[i];
For(i,1,n) c[i]=low(i);
Rof(i,n,1) b[i]=jump(a[i])+1,add(b[i],-1);
For(i,1,n) cout<<b[i]<<"\n";
return 0;}