HDU 5592 ZYB's Premutation（二分+树状数组）
最后更新于：2022-04-01 15:52:46
昨晚有事没打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;
}
~~~