UVA - 11525 Permutation

題意：求1-k的排列中第n大的序列，題目給出n的計算方法：

n = si*(k-1)+s2*(k-2)...+sk*0!; 並給你s1-sk

思路：首先我們明確，比如321是集合{1，2，3}的第幾大的序列，從第一位開始3開頭的話，那麼顯然這個序列的前面就一定會有1，2開頭的學列，就是2*2!,依次類推我們就可以確定這個學列是第幾大的了，但是要注意到用過的數將不再被我們考慮在內，現在這道題目是反過來了，可以琢磨一下si的含義是剩下沒用的數中第（si+1）大的數，我們通過線段樹來處理，0，1，分別代表沒使用過和使用過

#include 
#include 
#include 
#include 
using namespace std;
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mid ((l+r)>>1)
const int MAXN = 100005;

int s[MAXN],k;
int T[MAXN*4];

void cal(int rt){
	T[rt] = T[lson] + T[rson];
}

void build(int rt, int l, int r){
	if (l == r){
		T[rt] = 1;
		return;
	}
	build(lson, l, mid);
	build(rson, mid+1, r);
	cal(rt);
}

int query(int rt, int l, int r, int x){
	if (l == r){
		T[rt] = 0;
		return l;
	}
	int ans;
	if (x <= T[lson])
		ans = query(lson, l, mid, x);
	else ans = query(rson, mid+1, r, x-T[lson]);
	cal(rt);
	return ans;
}

int main(){
	int t;
	scanf("%d", &t);
	while (t--){
		scanf("%d", &k);
		build(1, 1, k);
		for (int i = 1; i <= k; i++)
			scanf("%d",&s[i]);
		for (int i = 1; i < k; i++)
			printf("%d ",query(1, 1, k, s[i]+1));
		printf("%d\n",query(1, 1, k, s[k]+1));
	}
	return 0;
}