昨晚有事没打BC，今天补一补， 这是昨晚第三题，对于一个1~n的序列， 告诉我们每个数前面有多少个比他大的数， 要求我们还原序列。 不难发现， 如果我们倒着看的话， 假设当前第i个数是ans[i]， 它前面有k个比他大的数， 那么他就是删除后面已经求出的数字后的数组中第k+1大的数。 该题a[i]表示的是第i个数的前缀逆序对数，设p[i]表示第i个位置上的数，a[i]-a[i-1]就是i前面比p[i]大的数的个数，我们倒着处理， 当我们处理完i后面的数之后， 第i个数就是剩下的数中第a[i] - a[i-1]+1大的数。 不难想到，将原序列的数当作树状数组的下标， 值为1， 这样就能利用bit快速求出比当前数大的数字还有多少个。 那么问题就是解决：如何快速求出第k个1的位置。 我想到的方法比较无脑， 二分位置， 然后用树状数组判断比k大还是小。 时间复杂度O(n*logn*logn) 。  由于对数时间复杂度非常小， 按照题目中的数据范围， logn*logn最大也就100多。 足以应付该题。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) a>b?a:b #define Min(a,b) a<b?a:b using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 50000+5; int T,n,m,bit[maxn],a[maxn],ans[maxn]; int sum(int x) { int ans = 0; while(x > 0) { ans += bit[x]; x -= x & -x; } return ans; } void add(int x, int d) { while(x <= n) { bit[x] += d; x += x & -x; } } int main() { scanf("%d",&T); while(T--) { memset(bit, 0, sizeof(bit)); scanf("%d",&n); for(int i=1;i<=n;i++) add(i, 1); for(int i=0;i<n;i++) { scanf("%d",&a[i]); } for(int i=n-1;i>=0;i--) { int v ; if(i == 0) v = a[i]; else v = a[i] - a[i-1]; int l = 1, r = n, m; while(r > l) { m = (r+l)/2; if(sum(n) - sum(m) > v) l = m + 1; else r = m; } ans[i] = r; add(r, -1); } printf("%d",ans[0]); for(int i=1;i<n;i++) printf(" %d",ans[i]); printf("\n"); } return 0; } ~~~