标签: 树状数组,hdoj - CheaSim Blog

[HDOJ5592] ZYB's Premutation

[HDOJ5592] ZYB’s Premutation

题意

ZYB有一个序列所有的逆序数前缀和,$a_1,a_2,a_3,…,a_n$,他们各个都表示从1到$i$的逆序数的前缀和。

题解

树状数组+二分

首先我们可以倒着看,对于最后一个数字,他的逆序数减前面的逆序数就代表着前面大于他的个数。所以我们就可以把问题转化为,已知数字$a_i$在前$i$个中的位置,求$a_i是多少。

我们可以用树状数组来维护,$sum(i)$表示到$i$代表着$i$是第几个数字,每当一个数字用过之后,他后面的数字都要-1,因为他们的排序相当于减少了一个,第四个数字变成第三个数字。


+n 没有想到这个序列是单调的,所以可以二分。居然想的是怎么让整个数组往前挪。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4 + 1000;
int T,n;
int a[maxn],b[maxn],ans[maxn],bit[maxn];
int lowbit(int x){
return x&-x;
}
int add(int x,int val){
for(int i=x;i<=n;i+=lowbit(i)){
bit[i] += val;
}
}
int query(int x){
int s = 0;
for(int i=x;i;i-=lowbit(i)){
s += bit[i];
}
return s;
}
int solve(int l,int r,int x){
int ans = 0;
while(l<=r){
int mid = l+r>>1;
int temp = query(mid);
if(temp >= x){
r = mid-1;
ans = mid;
}else{
l = mid+1;
}
}
return ans;
}
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(bit,0,sizeof(bit));
memset(ans,0,sizeof(ans));
rep(i,1,n+1) add(i,1);
rep(i,1,n+1) scanf("%d",a+i);
rep(i,1,n+1) b[i] = a[i] - a[i-1];
per(i,1,n+1){
int pos = i-b[i];
ans[i] = solve(1,n,pos);
add(ans[i],-1);
}
rep(i,1,n+1){
printf("%d%c",ans[i],i==n?'\n':' ');
}
}
return 0;
}