题解

问题分析

这是一个差分约束系统问题。我们需要根据区间第 $k$ 小的约束条件，构造一个二进制数组。

关键观察

1. 前缀和转化：定义前缀和 $S[i] = A[0] + A[1] + \dots + A[i-1]$
2. 约束转化：区间 $[l, r]$ 中 $1$ 的个数为 $S[r+1] - S[l]$
3. 第 $k$ 小值约束：
   • 如果第 $k$ 小是 $0$，说明 $0$ 的数量至少为 $k$，即 $1$ 的数量最多为 $(r-l+1) - k$
   • 如果第 $k$ 小是 $1$，说明 $1$ 的数量至少为 $(r-l+1) - k + 1$

算法思路

差分约束系统 + SPFA 判负环：

约束条件转化

1. 基本约束：$0 \leq S[i+1] - S[i] \leq 1$
2. 第 $k$ 小为 $0$：$S[r+1] - S[l] \leq (r-l+1) - k$
3. 第 $k$ 小为 $1$：$S[l] - S[r+1] \leq -((r-l+1) - k + 1)$

图构建

• 节点：$S[0], S[1], \dots, S[n]$
• 边：
  • $S[i] \to S[i+1]$，权值 $1$（$S[i+1] - S[i] \leq 1$）
  • $S[i+1] \to S[i]$，权值 $0$（$S[i] - S[i+1] \leq 0$）
  • 根据约束条件添加相应边

核心代码逻辑

图构建

// 基本约束
for (int i = 1; i <= n; ++i) {
    E[i - 1].emplace_back(i, 1);      // S[i] - S[i-1] <= 1
    E[i].emplace_back(i - 1, 0);      // S[i-1] - S[i] <= 0
}

// 约束条件转化
if (v == 0) {
    E[l - 1].emplace_back(r, r - l + 1 - k);  // S[r] - S[l-1] <= (r-l+1)-k
} else {
    E[r].emplace_back(l - 1, -(r - l + 1 - k + 1));  // S[l-1] - S[r] <= -((r-l+1)-k+1)
}

SPFA 求解

std::vector<int> dist(n + 1, 0x3fffffff), inqueue(n + 1, 0), cnt(n + 1, 0);
std::queue<int> q;
dist[0] = 0;
q.push(0);

while (!q.empty()) {
    int u = q.front(); q.pop();
    inqueue[u] = 0;
    
    for (auto &[v, w] : E[u]) {
        if (dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w;
            cnt[v]++;
            if (cnt[v] > n) {  // 负环检测
                puts("-1");
                return 0;
            }
            if (!inqueue[v]) {
                q.push(v);
                inqueue[v] = 1;
            }
        }
    }
}

算法步骤

1. 读入 $N, M$ 和约束条件
2. 构建图：根据约束条件建立差分约束系统
3. SPFA求解：计算最短路径，检测负环
4. 输出结果：根据 $S[i] - S[i-1]$ 还原原数组
5. 无解判断：发现负环则输出 $-1$

复杂度分析

• 图构建：$O(N + M)$
• SPFA：最坏 $O(NM)$，在 $N \leq 5000, M \leq 10000$ 时可接受
• 总复杂度：$O(NM)$

样例验证

样例输入：

4 5
0 1 2 1
0 2 2 0
2 2 1 0
0 1 1 0
1 2 1 0

求解过程：

• 前缀和 $S = [0, 0, 1, 1, 1]$
• 原数组 $A = [0, 1, 0, 0]$ ✓

算法标签

• 差分约束系统
• 图论
• 最短路径
• SPFA算法
• 负环检测
• 前缀和技巧