ZYBZYBZYB有一个排列PPP,但他只记得PPP中每个前缀区间的逆序对数,现在他要求你还原这个排列.
(i,j)(i<j)(i,j)(i < j)(i,j)(i<j)被称为一对逆序对当且仅当Ai>AjA_i>A_jA?i??>A?j??
第一行一个整数TTT表示数据组数。
接下来每组数据：
第一行一个正整数NNN,描述排列的长度.
第二行NNN个正整数AiA_iA?i??,描述前缀区间[1,i][1,i][1,i]的逆序对数.
数据保证合法.
1≤T≤51 \leq T \leq 51≤T≤5,1≤N≤500001 \leq N \leq 500001≤N≤50000
TTT行每行NNN个整数表示答案的排列.
1 3 0 1 2
3 1 2
心得：爆炸；ＢＯＯＭＢＯＯＭＢＯＯＭ；runtime errer了６次！！！！
只好瞄眼隔壁的了；树状数组+二分
#include<cstdio> #include<cstring> #include<iostream> using namespace std ; const int maxn = 50010 ; int tree[maxn] ; int n ; int getsum(int x){ int sum = 0 ; while(x){ sum += tree[x] ; x -= x&(-x) ; } return sum ; } void update(int x , int dx){ while(x <= n){ tree[x] += dx ; x += x&(-x) ; } } int find(int x , int ss){ int l = 1 ; int r = n ; while(l <= r){ int mid = (l + r) >> 1; int sum = ss-(mid-getsum(mid)) ; if(sum > x){ l=mid+1; } else if(sum <= x){ r=mid-1 ; } } return r+1 ; } int a[maxn] ; int ans[maxn] ; int main() { int t ; scanf("%d" , &t) ; while(t--){ scanf("%d" , &n) ; for(int i = 1;i <= n;i++){ scanf("%d" , &a[i]) ; tree[i] = 0 ; } for(int i = n;i >= 1;i--){ int sum = a[i] - a[i-1] ; ans[i] = find(sum , i) ; update(ans[i] , 1) ; } for(int i = 1;i <= n;i++){ printf("%d%c" , ans[i] , i == n ?‘\n‘:‘ ‘) ; } } return 0; }
BestCoder Round #65 （ZYB's Premutation）
原文：http://www.cnblogs.com/yoyo-sincerely/p/5022413.html