题目详解：F. Almost Permutation

问题重述

我们有一个长度为 $n$ 的数组 $a$，每个元素满足 $1 \le a_i \le n$。给定 $q$ 条区间约束，每条约束形如：

• 类型 $1$：$\forall x \in [l_i, r_i],\ a_x \ge v_i$
• 类型 $2$：$\forall x \in [l_i, r_i],\ a_x \le v_i$

定义数组的代价为 $\sum_{i=1}^{n} (\text{cnt}(i))^2$，其中 $\text{cnt}(i)$ 是数字 $i$ 在数组中的出现次数。

要求：在满足所有约束的条件下，最小化这个代价。如果无解，输出 $-1$。

数据范围

• $1 \le n \le 50$
• $0 \le q \le 100$

---

核心解题思路

本题的核心难点在于代价函数 $\sum (\text{cnt}(i))^2$ 是非线性的，无法直接用线性规划或网络流处理。我们需要将其转化为线性形式。

关键转化：平方和的线性化

考虑一个数字 $i$ 在数组中出现 $k$ 次，它对代价的贡献是 $k^2$。而 $k^2$ 可以写成：

$$k^2 = \sum_{j=1}^{k} (2j - 1)$$

例如：

• $k = 1$：$1^2 = 1 = 2 \times 1 - 1$
• $k = 2$：$2^2 = 4 = 1 + 3$
• $k = 3$：$3^2 = 9 = 1 + 3 + 5$
• $k = 4$：$4^2 = 16 = 1 + 3 + 5 + 7$

直观理解：数字 $i$ 的第 $j$ 次出现（按出现顺序）产生额外代价 $2j - 1$。由于我们最小化总代价，算法会优先使用较小的 $j$（即更便宜的“第几次出现”）。

这样，我们把每个数字 $i$ 拆成 $n$ 个“使用机会”，第 $j$ 次机会的代价是 $2j - 1$。

---

建模为最小费用最大流

节点设计

我们将问题建模为一个流网络，包含四类节点：

1. 源点 $S$：流量起点
2. 数字节点 $D_i$（$1 \le i \le n$）：代表数字 $i$
3. 使用次数节点 $U_{i,j}$（$1 \le i \le n, 1 \le j \le n$）：代表数字 $i$ 的第 $j$ 次使用
4. 位置节点 $P_p$（$1 \le p \le n$）：代表数组中的位置 $p$
5. 汇点 $T$：流量终点

节点总数：$1 + n + n^2 + n + 1 = O(n^2)$，当 $n=50$ 时约 $2600$ 个节点，完全可行。

边的设计与含义

第一层：源点 → 数字节点

• 对于每个数字 $i$（$1 \le i \le n$）：添加边 $S \to D_i$，容量为 $n$，费用为 $0$
• 含义：数字 $i$ 最多可以被使用 $n$ 次（实际最多 $n$ 次，因为总共只有 $n$ 个位置）

第二层：数字节点 → 使用次数节点

• 对于每个数字 $i$ 和每个使用次数 $j$（$1 \le j \le n$）：添加边 $D_i \to U_{i,j}$，容量为 $1$，费用为 $2j - 1$
• 含义：数字 $i$ 的第 $j$ 次使用需要支付代价 $2j - 1$。每个使用机会只能被选一次（容量 $1$）

第三层：使用次数节点 → 位置节点

• 对于每个 $U_{i,j}$ 和每个位置 $p$（$1 \le p \le n$）：如果 $L_p \le i \le R_p$，添加边 $U_{i,j} \to P_p$，容量为 $1$，费用为 $0$
• 含义：如果数字 $i$ 在位置 $p$ 的取值范围内，就可以把这次“使用机会”分配到该位置

这里 $L_p$ 和 $R_p$ 是通过所有区间约束计算出的位置 $p$ 的取值范围：

• 初始：$L_p = 1, R_p = n$
• 类型 $1$ 约束 $[l, r] \ge v$：对所有 $p \in [l, r]$，$L_p = \max(L_p, v)$
• 类型 $2$ 约束 $[l, r] \le v$：对所有 $p \in [l, r]$，$R_p = \min(R_p, v)$

第四层：位置节点 → 汇点

• 对于每个位置 $p$：添加边 $P_p \to T$，容量为 $1$，费用为 $0$
• 含义：每个位置必须恰好填一个数字（因为总流量为 $n$）

流量需求

我们从源点 $S$ 发送 $n$ 个单位的流量到汇点 $T$。这 $n$ 个流量单位对应数组的 $n$ 个位置。

• 每个单位流量从 $S$ 出发，经过某个数字节点 $D_i$，然后经过某个使用次数节点 $U_{i,j}$，再经过某个位置节点 $P_p$，最后到达 $T$。
• 这条路径表示：在位置 $p$ 填入数字 $i$，并且这是数字 $i$ 的第 $j$ 次出现。
• 路径的费用就是 $U_{i,j}$ 边的费用 $2j - 1$。

由于每个 $U_{i,j}$ 容量为 $1$，数字 $i$ 的第 $j$ 次使用最多被选一次。如果数字 $i$ 最终出现 $k$ 次，那么它必然使用 $U_{i,1}, U_{i,2}, \dots, U_{i,k}$ 这些边，总费用为：

$$\sum_{j=1}^{k} (2j - 1) = k^2$$

完美符合代价定义。

---

算法步骤

步骤 1：计算每个位置的可选值范围

for (int i = 1; i <= n; i++) {
    L[i] = 1;
    R[i] = n;
}
for (每条约束) {
    if (t == 1) { // >= v
        for (int j = l; j <= r; j++) L[j] = max(L[j], v);
    } else { // <= v
        for (int j = l; j <= r; j++) R[j] = min(R[j], v);
    }
}

步骤 2：可行性检查

如果存在 $i$ 使得 $L[i] > R[i]$，说明某个位置没有可选数字，输出 $-1$。

步骤 3：建图并运行最小费用最大流

使用 Dijkstra 优化的最小费用流算法（势函数 $h$ 处理负权边）。

步骤 4：输出结果

• 如果最大流 $< n$，输出 $-1$
• 否则输出最小费用

---

复杂度分析

• 节点数：$O(n^2)$

• 边数：

  • 第一层：$n$ 条
  • 第二层：$n^2$ 条
  • 第三层：$n^3$ 条（最坏情况，每个 $U_{i,j}$ 连接到所有 $n$ 个位置）
  • 第四层：$n$ 条

  总边数 $O(n^3) = O(125000)$，当 $n=50$ 时完全可接受。

• 最小费用流复杂度：$O(F \cdot E \log V)$，其中 $F = n$，$E = O(n^3)$，$V = O(n^2)$。 最坏情况约 $50 \times 125000 \times \log 2600 \approx 6 \times 10^7$ 次操作，在 3 秒内可行。

---

示例验证

示例 1

3 0

所有 $L_i=1, R_i=3$。最小代价的数组是排列 $1,2,3$（或任意排列，但平方和最小为 $1^2+1^2+1^2=3$）。输出 $3$。

示例 2

3 1
1 1 3 2

约束：所有位置 $\ge 2$。每个位置只能从 $\{2,3\}$ 中选。最优方案：$2,2,3$（$cnt(2)=2,cnt(3)=1$，代价 $2^2+1^2=5$）。无法使用数字 $1$，因为 $1<2$。

示例 3

3 2
1 1 3 2
2 1 3 2

约束：所有位置 $\ge 2$ 且 $\le 2$，所以每个位置必须填 $2$。数组为 $2,2,2$，代价 $3^2=9$。

示例 4

3 2
1 1 3 2
2 1 3 1

约束：所有位置 $\ge 2$ 且 $\le 1$，不可能，输出 $-1$。

---

核心总结

1. 平方和线性化：利用 $k^2 = \sum_{j=1}^{k} (2j-1)$ 将非线性代价转化为线性边的费用
2. 网络流建模：将“数字的使用次数”作为中间节点，自然实现了按顺序累加代价
3. 约束预处理：通过区间约束计算每个位置的可选值范围，简化了图的条件边
4. 最小费用最大流：求恰好 $n$ 个单位流量的最小费用，若流量不足则无解

这个模型是处理“最小化平方和分配问题”的经典技巧，可以推广到类似的问题中。