现在给定k和n，要你按字典序输出 第n种排列的数列
而且题目给的 n是 n=S1（k-1）！+S2(k-2)!+…+Sk-1*1!+Sk*0!(0=<Si<=k-i),
我们可以知道si表示i后面有多少个比a[i]小的数，这样一来首先想到的就是set，但是set不能顺序访问，所以可以用树状数组，，初始时置1，消除后置0，然后二分来求和为si+ 1的位置
代码如下：
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> #include<map> #include<queue> #include<stack> #include<string>#include<map> #include<set>using namespace std; #define LL long long const int maxn = 50005;const int INF = 1000000000;//freopen("input.txt", "r", stdin);int c[2 * maxn], s[maxn], ans[maxn], k;int lowbit(int x) {return x&(-x);}int sum(int x) {int ret = 0;while(x > 0) {ret += c[x];x -= lowbit(x);}return ret;}void add(int x) {while(x <= k) {c[x] += 1; x += lowbit(x);}}void subtract(int x) {while(x <= k) {c[x] -= 1; x += lowbit(x);}}int main() {int t; scanf("%d", &t);while(t–) {memset(c, 0, sizeof(c));cin >> k;for(int i = 1; i <= k; i++) add(i);for(int i = 1; i <= k; i++) {int tmp; cin >> tmp;int le = 1, ri = k;while(le < ri) {int mi = (le + ri) >> 1;int tsum = sum(mi);if(sum(mi) >= tmp + 1) ri = mi;else le = mi + 1;}ans[i] = ri;subtract(ans[i]);}printf("%d", ans[1]);for(int i = 2; i <= k; i++) printf(" %d", ans[i]);printf("\n");}return 0;}
如果说，罗马是一座厚重和凝固的堡垒，
