题意简述：给定一个长度为 \(n\) 序列 \(h\)。你可以交换两个相邻的 \(h\)，但它们也会随之取相反数。问使 \(h\) 不降的最小操作次数，若不可能则输出 \(-1\)。
关键转化：先给每个 \(h_i\) 乘上 \((-1)^i\)，然后问题转化为找到一个逆序对数最少的排列 \(p\)，使得 \(\forall i \in [1, n),~(-1)^ih_{p_i} \le (-1)^{i + 1}h_{p_{i + 1}}\)。
设 \(f(i, 0 / 1)\) 表示填到绝对值从大到小的第 \(i\) 个数，左侧长度的奇偶性为 \(0/1\) 的最小逆序对数。
先考虑绝对值不同时的转移，每次只需要计算填的数和中间空白段间的逆序对数就好套个 BIT 优化就能做到 \(\mathcal O(n \log n)\)。
然后加入绝对值相同的情况，可以能往左放就都往左放，然后依次把能右移的右移统计贡献。
都往左放时，我们贪心地尽量按原位置顺序排，右移的时候我们也从原位置大的开始，这样能使逆序对数尽可能小。
往右移的时候要分两种情况讨论：
- 右移不会影响数值正负时，直接右移每个数统计贡献即可。
- 右移会影响数值正负时，两项交叉位移。
时间复杂度同样是 \(\mathcal O(n \log n)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 5e5 + 10;
constexpr ll inf = 0x3f3f3f3f3f3f3f3fll;
int n, A[N], B[N], pos[N];
ll f[N][2], c[N][2];
struct Node {
int h, p;
bool operator<(const Node &rhs) const {
if (abs(h) == abs(rhs.h)) return h == rhs.h ? p < rhs.p : h < rhs.h;
return abs(h) < abs(rhs.h);
}
} a[N];
namespace BIT {
int c[N];
void fix(int x, int val = 1) {for (int i = x; i <= n; i += i & (-i)) c[i] += val;}
int query(int x) {int res = 0; for (int i = x; i; i -= i & (-i)) res += c[i]; return res;}
}
ll calc(int len) {
ll res = 0;
for (int i = 1; i <= len; i++) if (!pos) return inf;
for (int i = 1; i <= len; i++) res += BIT::query(n) - BIT::query(pos[i]), BIT::fix(pos[i]);
for (int i = 1; i <= len; i++) BIT::fix(pos[i], -1);
return res;
}
bool geto(int o, int x) {return (x & 1) ^ o ^ 1;}
ll dp(int cur, int o) {
if (f[cur][o] != -1) return f[cur][o];
if (!cur || !a[cur].h) return 0;
int nxt = cur; while (nxt > 1 && abs(a[nxt - 1].h) == abs(a[cur].h)) nxt--;
int totA = 0, totB = 0;
for (int i = nxt; i <= cur; i++) (a[i].h < 0 ? A[++totA] : B[++totB]) = a[i].p;
int len = cur - nxt + 1, cntA = 0, cntB = 0;
for (int i = 1; i <= len; i++) pos[i] = geto(o, i) ? A[++cntA] : B[++cntB];
ll f0 = inf, f1 = inf;
if ((len & 1) != (cur & 1)) {
if (cntA == totA && cntB == totB) {
ll s = calc(len);
for (int i = 1; i <= len; i++) s += c[pos[i]][0];
for (int i = len; i >= 0; i--) {
geto(o, i) ? f0 = min(f0, s) : f1 = min(f1, s);
s += c[pos[i]][1] - c[pos[i]][0];
}
}
} else {
int p = len;
if (cntA != totA || cntB != totB) {
cntA = cntB = 0, p--;
for (int i = 1; i < len; i++) pos[i] = geto(o, i) ? A[++cntA] : B[++cntB];
pos[len] = geto(o, len) ? B[++cntB] : A[++cntA];
}
if (cntA == totA && cntB == totB) {
ll s = calc(len);
for (int i = 1; i <= p; i++) s += c[pos[i]][0];
for (int i = p + 1; i <= len; i++) s += c[pos[i]][1];
for (int i = p; i >= 0; i -= 2) {
geto(o, i) ? f0 = min(f0, s) : f1 = min(f1, s);
if (i >= 2) {
s += c[pos[i]][1] + c[pos[i - 1]][1] - c[pos[i]][0] - c[pos[i - 1]][0];
(pos[i - 1] < pos[i]) ? s++ : s--;
}
}
}
}
return f[cur][o] = min(inf, min(f0 + dp(nxt - 1, 0), f1 + dp(nxt - 1, 1)));
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
cin >> n; for (int i = 1; i <= n; i++) a[i].p = i, cin >> a[i].h;
for (int i = 1; i <= n; i += 2) a[i].h = -a[i].h;
sort(a + 1, a + n + 1); int j = 1;
for (int i = 1; i <= n; i++) {
while(abs(a[j].h) < abs(a[i].h)) BIT::fix(a[j++].p);
c[a[i].p][0] = BIT::query(a[i].p - 1), c[a[i].p][1] = BIT::query(n) - BIT::query(a[i].p);
}
memset(BIT::c, 0, sizeof(BIT::c)), memset(f, -1, sizeof(f));
cout << (dp(n, 0) < inf ? dp(n, 0) : -1);
return 0;
}