通过模拟之后我们发现对于每一个位置上的数他都有一个规律,那就是先左移然后在右移。然后仔细发现可以知道,先右移的距离是前面比该数大的个数。右移就直接右移到目标位置了。然后用一个树状数组从左到右边扫边加就可以计算出答案了。

#include<bits/stdc++.h>
using namespace std; const int maxn = 1e5 + ;
int tr[maxn], in[maxn], l[maxn], r[maxn], n; int lb(int x){
return x & -x;
} void add(int adr, int val){
while(adr <= n){
tr[adr] += val;
adr += lb(adr);
}
} int sum(int adr){
int ret = ;
while(adr){
ret += tr[adr];
adr -= lb(adr);
}
return ret;
} int main(){
int T;scanf("%d", &T);
for(int ncase = ; ncase <= T; ncase ++){
scanf("%d", &n);
for(int i = ; i <= n; i ++) tr[i] = ;
for(int i = ; i <= n; i ++){
scanf("%d", &in[i]);
l[in[i]] = r[in[i]] = i;
l[in[i]] = min(l[in[i]], sum(in[i]));
r[in[i]] = max(r[in[i]], in[i]);
add(in[i], );
}
printf("Case #%d:", ncase);
for(int i = ; i <= n; i ++) printf(" %d",r[i] - l[i] - );printf("\n");
}
return ;
}
04-02 22:47