244. 谜一样的牛

题目链接：https://www.acwing.com/problem/content/description/245/

思路

计算末尾的牛身高的时候，可以发现就是求他在剩余可选身高中排第几的问题。可以用树状数组算query(r)：前r身高还有多少个。这样对于一头牛说，前面比他低的还有t牛，那么就需要找到第一个query(r) == t+1 ,r就是这头牛的身高。因为树状数组是计算前缀和，所以可以二分操作这个过程

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;

int N;
int arr[maxn],ans[maxn];
int tr[maxn];

int lowbit(int x){
    return x&-x;
}
void add(int idx,int v){
    for(int i = idx;i<=N;i += lowbit(i)) tr[i] += v;
}
int query(int r){
    int sum = 0;
    for(int i = r;i>=1;i -= lowbit(i)) sum += tr[i];
    return sum;
}
int main(){
    cin>>N;
    for(int i = 1;i<=N;i++) add(i,1);
    for(int i = 2;i<=N;i++) scanf("%d",&arr[i]);
    for(int i = N;i>=1;i--){
        int l = 1,r = N,mid;
        while(l<r){
            mid = (l+r)>>1;
            if(query(mid)  >= arr[i] + 1) r = mid;
            else l = mid+1;
        }
        ans[i] = l;
        add(l,-1);
    }
    for(int i = 1;i<=N;i++) printf("%d\n",ans[i]);

    return 0;
}