[JOISC2014]たのしい家庭菜園

题目大意：

给定一个长度为\(n(n\le3\times10^5)\)的序列\(A(A_i\le10^9)\)。只能交换相邻两个数，问最少需要几步可以将它变成一个单峰序列。

思路：

对于每个元素，看它两边哪边比他大的数少，就把它移到哪边。用树状数组维护即可，时间复杂度\(\mathcal O(n\log n)\)。

源代码：

#include<cstdio>
#include<cctype>
#include<climits>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
typedef long long int64;
const int N=3e5+1;
int n,a[N],b[N],c[N];
class FenwickTree {
private:
int val[N];
int lowbit(const int &x) const {
return x&-x;
}
public:
void reset() {
std::fill(&val[1],&val[n]+1,0);
}
void modify(int p) {
for(;p;p-=lowbit(p)) {
val[p]++;
}
}
int query(int p) const {
int ret=0;
for(;p<=n;p+=lowbit(p)) {
ret+=val[p];
}
return ret;
}
};
FenwickTree t;
int main() {
n=getint();
for(register int i=1;i<=n;i++) {
a[i]=b[i]=getint();
}
std::sort(&b[1],&b[n]+1);
for(register int i=1;i<=n;i++) {
a[i]=std::lower_bound(&b[1],&b[n]+1,a[i])-b;
}
std::fill(&c[1],&c[n]+1,INT_MAX);
for(register int i=1;i<=n;i++) {
t.modify(a[i]);
c[i]=std::min(c[i],t.query(a[i]+1));
}
t.reset();
for(register int i=n;i>=1;i--) {
t.modify(a[i]);
c[i]=std::min(c[i],t.query(a[i]+1));
}
int64 ans=0;
for(register int i=1;i<=n;i++) {
ans+=c[i];
}
printf("%lld\n",ans);
return 0;
}