昨晚有事沒打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; } ~~~