Uva(11525)(Permutation)

链接：https://vjudge.net/problem/UVA-11525
思路：一开始看到式子头皮发麻，后来查了一下是康拓展开的逆式，没学过正好学习了一下，Sk就表示当前位置排的是还剩下的数字中第k小的数，看到这里自然想到了树状数组求前缀和了，然后对于位置应该二分求解，二分注意一下跟普通的二分有些不同，还需记录当前位置的数字是否使用过。需要对二分相等的情况进行特殊处理一下
代码：

#include<bits/stdc++.h>
using namespace std;

int t,n;
const int maxn = 5e4+100;
int c[maxn<<1];
int j[maxn];

int lowbit(int x){
    return x&(-x);
}

void add(int x,int d){
    while(x<=n){
        c[x]+=d;
        x+=lowbit(x);
    }
}

int sum(int x){
    int res = 0;
    while(x){
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}

int cc(int d,int p){
   if (sum(d-1)>p) return 1;
   if (sum(d-1)==p)return 0;
   if(sum(d-1)<p)return -1;
}

int main(){
    scanf("%d",&t);
    while(t--){
        memset(c,0,sizeof(c));
        memset(j,0,sizeof(j));
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            add(i,1);
        }
    int now;
    for(int i=0;i<n;i++){
        scanf("%d",&now);
        int ub = n;
        int lb = 0;
        while(ub>lb){
            int mid = (ub+lb)/2;
            int res = cc(mid,now);
            if(res==1)ub = mid;
            else if(res==0&&j[mid])lb = mid+1;//等于且使用过该数字，则要的值一定在后面
            else if(res==0&&!j[mid]){//未使用则及时跳出
                ub = mid;
                break;
            }
            else lb = mid+1;
            if(ub==lb&&j[ub]){
                while(j[ub])ub++;
                break;
            }
        }
        j[ub] = 1;
        add(ub,-1);
        printf("%d%c",ub,i==n-1?'\n':' ');
    }
    }
    return 0;
}