题解：线条小镇（Line Town）

问题分析

核心问题

给定$N$个居民的幸福值序列$h_1, h_2, ..., h_N$，每次可交换相邻居民，交换后两人幸福值取反。需判断能否通过若干次交换使序列非递减，若可行输出最少交换次数，否则输出$-1$。

关键观察

1. 交换的双重影响：相邻交换不仅改变位置，还会翻转两个元素的符号。设交换位置$i$和$i+1$的元素$x$和$y$，交换后变为$-y$和$-x$。
2. 符号与位置的关联：元素经过$k$次交换后，符号翻转次数等于交换次数（每次交换参与元素翻转1次）。设元素初始位置为$pos$，最终位置为$final-pos$，交换次数为$t$，则最终符号为$(-1)^t \times 初始符号$。
3. 目标序列的约束：最终非递减序列中，元素的绝对值必须满足非递减（因符号翻转不改变绝对值），且符号需与位置相关联（由交换次数推导）。

算法思路

1. 预处理与编码

• 符号状态转换：定义$b[i] = (h[i] < 0) \oplus (i \& 1)$，表示元素$h[i]$的初始符号状态（结合位置奇偶性）。
• 绝对值离散化：提取所有非零元素的绝对值，排序去重后离散化，将原元素转换为编码（正元素编码为正，负元素编码为负），便于后续分组处理。
• 分组存储：按离散化后的绝对值分组，每组存储两个列表：对应符号状态$0$和$1$的元素初始位置。

2. 可行性判定核心

对于每个绝对值分组$c$，设该组中符号状态$0$的元素个数为$cnt0$，状态$1$的个数为$cnt1$，定义差值$d = cnt0 - cnt1$。若$|d| > 2$，则无法通过交换组合出合法序列，直接返回$-1$。

3. 最小交换次数计算

使用动态规划（DP）维护状态，结合树状数组（BIT）计算逆序对（交换次数本质是逆序对数量）：

• DP状态定义：$f[x][y]$表示处理完部分分组后，当前序列首尾的符号状态为$x$和$y$时的最小交换次数。
• 树状数组作用：维护元素位置信息，快速计算元素移动过程中产生的交换次数（逆序对数量）。
• 状态转移：按绝对值从大到小处理分组（保证非递减约束），根据每组的$d$值（$cnt0 - cnt1$）枚举合法的状态转移路径，结合树状数组计算的交换次数更新DP状态。

4. 细节处理

• 左右侧交换次数计算：使用两个树状数组$TL$和$TR$分别维护左侧和右侧未处理元素的位置，计算元素移动时与左侧、右侧元素的逆序对数量。
• 状态转移分类：根据每组$d$值（$-2, -1, 0, 1, 2$）分类处理，确保转移过程符合符号状态约束，且交换次数最小。

代码解析

数据结构

• 树状数组（BIT1）：3个实例$TL$、$TR$、$TO$，分别用于计算左侧逆序对、右侧逆序对和临时标记。$TR$的op=1表示反向存储，适配右侧计算。
• DP数组：$f[2][2]$存储当前DP状态，$g[2][2]$存储下一轮状态（避免覆盖）。
• 辅助数组：$L[2][MAXN]$和$R[2][MAXN]$分别存储左侧和右侧交换次数的前缀和。

核心流程

1. 输入处理与编码：读取数据，计算$b[i]$，离散化绝对值，分组存储位置。
2. 初始化：初始化树状数组（标记所有位置为未处理），DP状态（初始状态为$f[0][n\&1] = 0$，其余为无穷大）。
3. 逆序处理分组：按离散化后的绝对值从大到小处理每组：
   • 标记当前组元素为已处理（从$TR$中移除）。
   • 计算该组左侧和右侧的交换次数前缀和$L$和$R$。
   • 根据$d$值分类进行DP状态转移，更新$g$数组。
   • 将$g$数组赋值给$f$，进入下一组处理。
4. 结果输出：最终DP状态的最小值即为答案，若最小值仍为无穷大则输出$-1$。

关键代码片段解释

离散化与分组

for (int i = 1; i <= n; ++i)
    if (a[i]) {
        if (a[i] > 0)
            a[i] = lower_bound(vl + 1, vl + m + 1, a[i]) - vl;
        else
            a[i] = vl - lower_bound(vl + 1, vl + m + 1, -a[i]);
        p[abs(a[i])][b[i]].push_back(i);
    }

将原元素转换为离散化编码，按绝对值和符号状态分组存储位置，为后续处理奠定基础。

树状数组计算交换次数

for (int i = 0; i < sz; ++i) {
    int x = p[c][i & 1][i / 2], y = p[c][i & 1].rbegin()[i / 2];
    TL.add(x, -1), L[o][i + 1] = L[o][i] + TL.qry(x);
    R[o][i + 1] = R[o][i] + TR.qry(y) + TO.qry(y), TO.add(y, 1);
}

通过树状数组$TL$计算元素与左侧未处理元素的逆序对数量，$TR$计算与右侧未处理元素的逆序对数量，累计得到前缀和$L$和$R$。

DP状态转移（以$d=0$为例）

for (int i = 0; i <= s; i += 2)
    for (int x : {0, 1})
        for (int y : {0, 1}) {
            g[x][y] = min(g[x][y], f[x][y] + L[x][i] + R[y][s - i]);
        }
for (int i = 1; i < s; i += 2) {
    g[1][0] = min(g[1][0], f[0][1] + L[0][i] + R[1][s - i]);
    g[0][1] = min(g[0][1], f[1][0] + L[1][i] + R[0][s - i]);
}

根据分组元素总数$s$和差值$d=0$，枚举合法的拆分方式（$i$为左侧选取个数），结合$L$和$R$的前缀和更新DP状态，确保交换次数最小。

复杂度分析

• 时间复杂度：$O(N \log N)$。离散化复杂度$O(N \log N)$，每组处理中树状数组操作复杂度$O(s \log N)$（$s$为组内元素个数），总复杂度为$O(N \log N)$（所有组$s$之和为$N$）。
• 空间复杂度：$O(N)$。用于存储分组、树状数组、DP状态等，均为线性空间。

边界情况与注意事项

1. 全零序列：零的符号翻转后仍为零，可直接判定为合法（非递减），交换次数为$0$。
2. 差值$|d|>2$：任何分组满足此条件时，无法组合出合法序列，直接返回$-1$。
3. DP状态初始化：初始状态需结合最后一个位置的奇偶性（$n\&1$），确保符号状态的一致性。