[JOISC2014]たのしい家庭菜園
题目大意：
给定一个长度为\(n(n\le3\times10^5)\)的序列\(A(A_i\le10^9)\)。只能交换相邻两个数，问最少需要几步可以将它变成一个单峰序列。
思路：
对于每个元素，看它两边哪边比他大的数少，就把它移到哪边。用树状数组维护即可，时间复杂度\(\mathcal O(n\log n)\)。
源代码：
#include#include #include #include 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;}