【题解】有趣的家庭菜园 树状数组 bzoj4240 ——quhengyi11

传送门喵

吐槽：竟然有一本教种菜的书跟这题同名

蛮巧妙的一道题。

首先一个结论，将每个菜再加一个位置 id，那么菜的高度合法的一种方案的最小交换次数=此时菜的 id 的逆序对数。

证明：初始的时候 id 数组逆序对个数的，考虑归纳法，当逆序对个数为 $k-1$的时候，我们证明有效的一次交换必定会使 id 的逆序对个数为 $k$

首先因为你是交换两个相邻的，操作前逆序对的个数和操作后逆序对个数的差值的绝对值肯定是 1，又因为你如果交换了原本 id 为逆序 (位置在前的 id 大) 的两个菜，使它们的 id 变为顺序 (位置在前的 id 小) 的，因为原来这两个菜的 id 关系一定是顺序的，那么我们只要不改变这两个菜原来的相对位置关系就不会使他们变成逆序的，也就不会再把它们改成顺序的了，因此有效操作逆序对数必定是+1 的。

然后你可以按高度从大到小加菜，因为是单峰函数，我们每次加菜的时候只能加在已有菜的两边，那么就贪心加菜就行了，加哪边使得菜的逆序对个数增加得最少就加哪边，因为初始一个菜的情况逆序对个数为 0，那么用归纳法我们也很容易知道这样贪心是正确的。

代码：

#include<bits/stdc++.h> 
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 10000000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
#define N 300005
#define ls (k << 1)
#define rs (k << 1 | 1)
#define M 260
int n, m;
struct node{
    int h, id;
    friend bool operator < (node x, node y)
    {
        return x.h > y.h;
    }
}t[N];
int t1[N], t2[N], sta[N], top;
ll ans;
inline void add1 (int x, int val) {for (int i = x; i <= n; i += lowbit(i)) t1[i] += val;}
inline int query1 (int x) {int ret = 0; for (int i = x; i; i -= lowbit(i)) ret += t1[i]; return ret;}
inline void add2 (int x, int val) {for (int i = x; i; i -= lowbit(i)) t2[i] += val;}
inline int query2 (int x) {int ret = 0; for (int i = x; i <= n; i += lowbit(i)) ret += t2[i]; return ret;}
int main ()
{
    scanf("%d", &n);
    fo (i, 1, n) {scanf("%d", &t[i].h); t[i].id = i;}
    std::sort(t + 1, t + n + 1);
    int i = 1; 
    while (i <= n)
    {
        sta[++top] = t[i].id; ++i;
        while (t[i].h == t[i - 1].h) {sta[++top] = t[i].id; ++i;}
        fo (j, 1, top)
            ans += std::min(query1(sta[j]), query2(sta[j]));
        while (top)
        {
            add1(sta[top], 1);
            add2(sta[top], 1);
            --top;
        }
    }
    printf("%lld\n", ans);
    return 0;
}