UVA_11525 树状数组的活用 二分

我们知道1——k有K！种排列，现在给定k和n，要你按字典序输出 第n种排列的数列

而且题目给的 n是 n=S1（k-1）！+S2(k-2)!+...+Sk-1*1!+Sk*0!(0=<Si<=k-i),

k最大为50000，直接算出来不可能，我发现这个n的表达式很有意思，明显（k-1）！就是表示第一次除第一个以外，剩下k-1个数的排列个数，乘一个S1就说明之前用了多少次这种排列了，根据这个 再手算了一下，发现就是，每次找第Sk个数，输出，当然已经访问过的数就要T出去

这很明显就是树状数组 （或者线段树的单点修改和查询）功能，先初始化每个都是大小为1，然后每次二分找第Sk个，找到之后，把该位置置为-1，消除该位的影响，继续找，继续输出即可。你看题目里给定的S的范围也就是顺应这个，故意把剩下几个数，S就恰好限定在这个里面

发现自己二分写的还不是很熟，一开始还搞了一下子，是用mid还是L做结果呢 最后在我的写法里被证明是用L做结果

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 50000+10

using namespace std;

int A[N];

int n;

int lowbit(int x)

{

    return x&(-x);

}

void add(int x,int v)

{

    while (x<=n){

        A[x]+=v;

        x+=lowbit(x);

    }

}

void init()

{

    for (int i=;i<=n;i++){

        add(i,);

    }

}

int query(int x)

{

    int ret=;

    while (x>){

        ret+=A[x];

        x-=lowbit(x);

    }

    return ret;

}

int main()

{

    int t;

    scanf("%d",&t);

    while (t--)

    {

      scanf("%d",&n);

      init();

      for (int i=;i<=n;i++){

        int a;

        scanf("%d",&a);

        int L=,R=n,mid;

        while (L<R)

        {

            mid=(L+R)>>;

            int tmp=query(mid);

            //if (tmp==a+1) break;

            if (tmp<a+) L=mid+;

            else R=mid;

        }

        //cout<<"@@"<<mid<<endl;

        add(L,-);

        printf("%d",L);

        if (i<n) putchar(' ');

      }

      puts("");

    }

    return ;

}