题目

矩阵X

题目链接点击跳转

解题思路（二维单调队列优化）

问题本质

给定 ​n \times m 矩阵，选择一个 恰好 ​n' \times m' 的连续子矩阵，最大化：

子矩阵大小固定为 ​n' \times m'

核心优化策略

1. 二维前缀和：​O(1) 查询任意子矩阵和
2. 二维单调队列：两次一维单调队列（先按行，再按列）​O(nm) 预处理所有 ​n' \times m' 子矩阵的极值

详细步骤

步骤1：二维前缀和预处理

• 构建前缀和数组 pref，使得 pref[i+1][j+1] 表示左上角 ​(0,0) 到右下角 ​(i,j) 的和
• 查询子矩阵和：sum = pref[r2+1][c2+1] - pref[r1][c2+1] - pref[r2+1][c1] + pref[r1][c1]

二维单调队列求窗口最大/最小值

如果直接对每个子矩阵暴力找 max/min，复杂度会炸。
思路：先横向滑，再纵向滑，把二维问题拆成两次一维滑动窗口。

第一步：对每一行做长度为 m' 的滑窗

对第 i 行，用单调队列维护：

• rowMax[i][j]：以 j 为右端点，长度 m' 的窗口最大值
• rowMin[i][j]：以 j 为右端点，长度 m' 的窗口最小值

这里 j 从 m' 到 m，表示窗口覆盖列 [j-m'+1, j]。

这一步复杂度：每行 O(m)，总 O(nm)。

第二步：在 rowMax / rowMin 上再对列做长度为 n' 的滑窗

现在把 rowMax 看成新矩阵：
对每一列 j，再做一次长度 n' 的滑窗：

• matMax[i][j]：以 i 为下端点的 n' 行内的最大值
• matMin[i][j]：对应最小值

此时 (i,j) 就对应原矩阵中一个
右下角在 (i,j)，大小为 ​n' \times m′ 的子矩阵。

再滑一次，复杂度还是 O(nm)。

步骤4：枚举所有合法子矩阵

• 遍历右下角 ​(i, j)（​i \geq n'-1, ​j \geq m'-1）
• 计算和 ​S、最大值 ​M、最小值 ​m
• 更新答案：​\max(S \times (M - m))

参考代码（Java代码）

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int nPrime = sc.nextInt();
        int mPrime = sc.nextInt();

        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = sc.nextInt();
            }
        }

        // 1. 构建二维前缀和数组
        long[][] pref = new long[n + 1][m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 计算前缀和：当前元素 + 上一行的前缀和 + 前一列的前缀和 - 左上角的重复部分
                pref[i + 1][j + 1] = a[i][j] + pref[i][j + 1] + pref[i + 1][j] - pref[i][j];
            }
        }

        // 2. 预处理行方向滑动窗口极值
        int[][] rowMax = new int[n][m]; // 每行长度为 m' 的窗口最大值
        int[][] rowMin = new int[n][m]; // 每行长度为 m' 的窗口最小值

        Deque<Integer> dq = new ArrayDeque<>();

        // 处理每行的最大值
        for (int i = 0; i < n; i++) {
            dq.clear();
            for (int j = 0; j < m; j++) {
                // 移除过期元素（窗口左边界外的元素）
                while (!dq.isEmpty() && dq.peekFirst() <= j - mPrime) {
                    dq.pollFirst();
                }

                // 维护单调递减队列（求最大值）
                while (!dq.isEmpty() && a[i][dq.peekLast()] <= a[i][j]) {
                    dq.pollLast();
                }
                dq.offerLast(j);

                // 当窗口大小达到 m' 时记录结果
                if (j >= mPrime - 1) {
                    rowMax[i][j] = a[i][dq.peekFirst()];
                }
            }
        }

        // 处理每行的最小值
        for (int i = 0; i < n; i++) {
            dq.clear();
            for (int j = 0; j < m; j++) {
                while (!dq.isEmpty() && dq.peekFirst() <= j - mPrime) {
                    dq.pollFirst();
                }
                while (!dq.isEmpty() && a[i][dq.peekLast()] >= a[i][j]) {
                    dq.pollLast();
                }
                dq.offerLast(j);
                if (j >= mPrime - 1) {
                    rowMin[i][j] = a[i][dq.peekFirst()];
                }
            }
        }

        // 3. 预处理列方向滑动窗口极值
        int[][] matMax = new int[n][m]; // 以 (i,j) 为右下角的 n'x m' 子矩阵最大值
        int[][] matMin = new int[n][m]; // 以 (i,j) 为右下角的 n'x m' 子矩阵最小值

        // 处理每列的最大值（对 rowMax 进行列方向滑动窗口）
        for (int j = mPrime - 1; j < m; j++) {
            dq.clear();
            for (int i = 0; i < n; i++) {
                // 移除过期行（窗口上边界外的行）
                while (!dq.isEmpty() && dq.peekFirst() <= i - nPrime) {
                    dq.pollFirst();
                }

                // 维护单调递减队列（求最大值）
                while (!dq.isEmpty() && rowMax[dq.peekLast()][j] <= rowMax[i][j]) {
                    dq.pollLast();
                }
                dq.offerLast(i);

                // 当窗口高度达到 n' 时记录结果
                if (i >= nPrime - 1) {
                    matMax[i][j] = rowMax[dq.peekFirst()][j];
                }
            }
        }

        // 处理每列的最小值（对 rowMin 进行列方向滑动窗口）
        for (int j = mPrime - 1; j < m; j++) {
            dq.clear();
            for (int i = 0; i < n; i++) {
                while (!dq.isEmpty() && dq.peekFirst() <= i - nPrime) {
                    dq.pollFirst();
                }
                while (!dq.isEmpty() && rowMin[dq.peekLast()][j] >= rowMin[i][j]) {
                    dq.pollLast();
                }
                dq.offerLast(i);
                if (i >= nPrime - 1) {
                    matMin[i][j] = rowMin[dq.peekFirst()][j];
                }
            }
        }

        // 4. 枚举所有合法子矩阵（右下角 (i,j)）
        long ans = 0;
        for (int i = nPrime - 1; i < n; i++) {
            for (int j = mPrime - 1; j < m; j++) {
                // 计算子矩阵和：左上角 (i-nPrime+1, j-mPrime+1) 到右下角 (i,j)
                // 前缀和计算：当前子矩阵和 = 整体 - 上边 - 左边 + 左上角重复部分
                long sum = pref[i + 1][j + 1] - pref[i - nPrime + 1][j + 1]
                        - pref[i + 1][j - mPrime + 1] + pref[i - nPrime + 1][j - mPrime + 1];

                // 获取最大值和最小值
                long maxVal = matMax[i][j];
                long minVal = matMin[i][j];

                // 计算乘积并更新答案
                long product = sum * (maxVal - minVal);
                ans = Math.max(ans, product);
            }
        }

        System.out.println(ans);
    }
}

复杂度分析

• 时间复杂度：​O(nm)
  • 二维前缀和：​O(nm)
  • 两次单调队列（行+列）：​O(nm)
  • 枚举子矩阵：​O(nm)
• 空间复杂度：​O(nm)
  • 存储前缀和、rowMax、rowMin、matMax、matMin

蓝桥部队

题目描述了一个蓝桥部队的场景，其中小明作为长官需要对 ​N 名军人和 1 名军师下达 ​M 条命令。命令分为两种类型：

1. 合并命令（1 x y）：让军人 ​x 所在列的所有人作为一个整体移动到和军人 ​y 所在列的后面，使两列合并为一列。
2. 查询命令（2 x y）：询问军师军人 ​x 和军人 ​y 是否站在同一列。若是，则军师要回应小明 ​x, y 之间有多少人，否则军师要回应 -1。

解题思路：带权并查集

为了高效地处理这两种命令，我们可以使用 带权并查集 来解决。

1. 并查集的基本概念

• 并查集（Union-Find Set）：一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
• 查找（Find）：确定元素属于哪一个子集。
• 合并（Union）：将两个子集合并成同一个集合。

2. 带权并查集

• 权值：在并查集中，每个节点可以附加一个权值，用于记录节点之间的某种关系（如距离、编号差等）。
• 路径压缩：在查找过程中，将节点直接指向根节点，加快后续查找速度。
• 按秩合并：合并时，将秩（树的高度或节点数）较小的树合并到秩较大的树上，保持树的平衡。

3. 具体应用

• 初始化：每个军人初始时自成一个集合，权值为0。
• 合并命令（1 x y）：
  • 找到军人 ​x 和军人 ​y 所在集合的根节点 ​root_x 和 ​root_y。
  • 将 ​root_x 所在集合合并到 ​root_y 所在集合。
  • 更新权值，记录合并后的相对位置关系。
• 查询命令（2 x y）：
  • 找到军人 ​x 和军人 ​y 所在集合的根节点 ​root_x 和 ​root_y。
  • 如果 ​root_x == root_y（即在同一集合中）：
    • 通过权值计算 ​x 和 ​y 之间的具体位置差，得到两人之间的人数。
  • 否则，返回 ​-1。

4. 实现细节

数组	作用	初始值
parent[]	指向父节点	i 自身
dist[]	当前节点到父节点的距离（相对偏移）	0
size[]	集合大小（用于合并时计算偏移）	1

1. dist[x] 的含义：
   • 表示 x 到其父节点的相对位置（x 在父节点后 dist[x] 个位置）
   • 通过路径压缩，最终 dist[x] 会更新为 x 到根节点的总距离
2. 合并操作（union(x, y)）：
   • 将 x 所在集合合并到 y 所在集合
   • 设置 dist[rx] = size[ry]（rx 是 x 的根，ry 是 y 的根）
   • 意义：x 所在集合整体移动到 y 所在集合后面，所以 rx（x 的根）到 ry 的距离 = y 所在集合的大小
3. 查询操作（query(x, y)）：若 x 和 y 在同一集合，间隔人数 = |dist[x] - dist[y]| - 1

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 军人数量（1~n）
        int m = sc.nextInt(); // 命令数量

        // 初始化并查集（1-indexed）
        int[] parent = new int[n + 1];
        int[] dist = new int[n + 1]; // 到父节点的相对距离
        int[] size = new int[n + 1];  // 集合大小

        // 初始化：每个军人自成一列
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            dist[i] = 0;
            size[i] = 1;
        }

        // 处理每条命令
        for (int i = 0; i < m; i++) {
            int cmd = sc.nextInt();
            int x = sc.nextInt();
            int y = sc.nextInt();

            if (cmd == 1) {
                // 合并命令：x所在列移动到y所在列后面
                union(x, y, parent, dist, size);
            } else {
                // 查询命令：返回x和y之间的人数
                int ans = query(x, y, parent, dist, size);
                System.out.println(ans);
            }
        }
    }

    // 查找根节点（递归路径压缩）
    private static int find(int x, int[] parent, int[] dist) {
        // 如果x不是根节点
        if (x != parent[x]) {
            // 1. 先递归找到x的父节点的根
            int root = find(parent[x], parent, dist);
            // 2. 更新x到根的距离 = x到父节点的距离 + 父节点到根的距离
            dist[x] += dist[parent[x]];
            // 3. 路径压缩：x直接指向根
            parent[x] = root;
        }
        return parent[x]; // 返回根节点
    }

    // 合并命令：将x所在集合合并到y所在集合
    private static void union(int x, int y, int[] parent, int[] dist, int[] size) {
        int rx = find(x, parent, dist); // x的根
        int ry = find(y, parent, dist); // y的根

        if (rx == ry) return; // 已在同一列，无需合并

        // 将rx所在集合合并到ry所在集合（x列合并到y列）
        parent[rx] = ry;
        // rx到ry的距离 = ry所在集合的大小（ry集合有size[ry]人，rx列将排在ry后面）
        dist[rx] = size[ry];
        // 更新ry所在集合的大小
        size[ry] += size[rx];
    }

    // 查询命令：返回x和y之间的人数
    private static int query(int x, int y, int[] parent, int[] dist, int[] size) {
        int rx = find(x, parent, dist); // x的根
        int ry = find(y, parent, dist); // y的根

        if (rx != ry) {
            return -1; // 不在同一列
        }
        // 间隔人数 = |x到根的距离 - y到根的距离| - 1
        return Math.abs(dist[x] - dist[y]) - 1;
    }
}

推导部分和

解题思路

方法一：DFS 预处理构建差分关系图

题目给出的每一条约束本质上都是形如：

区间 ([l, r]) 的和等于 (s)

如果设前缀和数组 (P)，其中 (P[i]) 表示前 (i) 个数的总和，那么上述条件可以转化为：

(P[r] - P[l-1] = s)

这就变成了：两个未知量之间的差值是一个已知常数。
因此，可以把每个前缀位置 (​ 0 \sim N ) 看成一个节点，把这种“差值关系”当作边来处理。

将约束转化为带权图

对每个条件 ((l, r, s))，令：

• 节点 (u = l - 1)
• 节点 (v = r)

有关系：

• 从 (u) 到 (v)：权值为 (+s)，表示 (P[v] = P[u] + s)
• 从 (v) 到 (u)：权值为 (-s)，表示 (P[u] = P[v] - s)

这样就得到了一张带权无向图，图中每条边都表示两个前缀和之间的差值关系。

利用 DFS 计算相对偏移量

DFS和BFS都可以做，因为题目保证不会出现矛盾的数据，即可以保证图中两点的任意路径的长度都是一致的

在同一个连通块中，只要任选一个节点作为“参考点”，就可以通过 DFS 沿着边不断累加权值，计算出：

当前节点的前缀和 − 参考点的前缀和

用数组 dist[x] 记录这个相对偏移量：

• 若从 cur 走到 next，边权为 w
• 则有：dist[next] = dist[cur] + w

这样，DFS 结束后，同一连通块内任意两个点 (u, v) 都满足：

(P[v] - P[u] = dist[v] - dist[u])

同时，用 componentId 记录每个节点属于哪个连通块。

回答查询

对于查询 ((l, r))，同样转成节点：

• (u = l - 1)
• (v = r)

分两种情况：

• 如果 (u) 和 (v) 不在同一个连通块中，说明它们之间没有任何已知约束，无法确定差值，输出 UNKNOWN。
• 如果在同一连通块中，则根据 DFS 得到的结果直接计算：

(P[r] - P[l-1] = dist[v] - dist[u])

即可在 (O(1)) 时间内回答。

方法特点

• 通过一次 DFS 预处理所有节点的相对关系。
• 每个查询只需常数时间判断和计算。
• 思路直观：把“前缀和差值”问题转化为“图上路径权值累加”问题，适合用于离线或静态查询场景。

方法二：带权并查集

这一方法同样基于前缀和思想，但不再显式建图和 DFS，而是用并查集在合并过程中维护差值关系，实现边读入边维护，适合在线处理。

用前缀和把区间和变成“差值约束”

设前缀和数组 (P)，其中 (P[i]) 表示前 (i) 项的和。
题目中的条件：

区间 ([l, r]) 的和为 (S)

可以转化为：

(P[r] - P[l-1] = S)

也就是说：两个前缀位置之间的差是已知的常数。
因此仍然把每个前缀下标 (​ 0 \sim N ) 当作并查集中的一个节点。

并查集里维护“到父节点的差值”

在普通并查集中，只关心连通性；
这里我们额外维护一个数组 weight[x]，表示：

weight[x] = P[x] - P[parent[x]]

也就是：节点 x 到其父节点的前缀和差值。

这样，如果一路向上找到根节点 root，并把路径上的权值累加起来，就可以得到：

P[x] - P[root]

即 x 相对于所在集合“参考点”的偏移量。

查找时顺便更新到根的差值

在 find(x) 过程中做路径压缩时：

• 先递归找到父节点的根 root
• 再把
  x 到父 + 父 到 root
  累加起来，更新为 x 到 root 的差值

这样，查找结束后：

• parent[x] 直接是根
• weight[x] 就表示 P[x] - P[root]

为后续合并和查询打好基础。

合并时建立两个集合之间的关系

当读入一个约束 ((l, r, S)) 时，对应：

• (u = l - 1)
• (v = r)
• 已知：(P[v] - P[u] = S)

分别找到它们的根 rootU、rootV，并且此时：

• weight[u] = P[u] - P[rootU]
• weight[v] = P[v] - P[rootV]

如果两个根不同，就需要把一个集合接到另一个下面。
假设让 rootU 指向 rootV，则必须设置一个合适的权值，使原有等式仍然成立。

根据：

可以推出：

也就是：

weight[rootU] = weight[v] - weight[u] - S

这样合并后，整个集合内的差值关系就保持一致了。

回答查询

查询 ((l, r)) 同样转成：

• (u = l - 1)
• (v = r)

先分别 find(u)、find(v)：

• 如果根节点不同，说明两者之间没有被任何约束连起来，结果无法确定，输出 UNKNOWN。
• 如果根相同，设为 root，则：

直接输出即可。

方法特点

• 不需要显式建图，边读入边合并。
• 每次操作复杂度接近 (O(1))，整体效率高。
• 通过在并查集中维护“到父节点的差值”，把差分关系自然地融入到连通性维护中，适合大规模数据和在线查询场景。

参考代码

方法一：DFS

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int Q = sc.nextInt();

        // 构建图：节点 0 ~ N
        List<List<long[]>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        // 添加边（双向）
        for (int i = 0; i < M; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            long s = sc.nextLong();
            int u = l - 1;
            int v = r;
            // u -> v: +s
            // v -> u: -s
            // 边的结构：目标节点和权重
            graph.get(u).add(new long[]{v, s});
            graph.get(v).add(new long[]{u, -s});
        }

        // dist[i] 表示 P[i] 相对于其连通块根的偏移（即 P[i] - P[root]）
        long[] dist = new long[N + 1];
        boolean[] visited = new boolean[N + 1];
        int[] componentId = new int[N + 1]; // 记录每个节点所属连通块编号
        int compCount = 0;

        // 对每个未访问节点进行 DFS
        for (int i = 0; i <= N; i++) {
            if (!visited[i]) {
                dfs(i, 0, compCount, graph, dist, visited, componentId);
                compCount++;
            }
        }

        // 处理查询
        for (int i = 0; i < Q; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            int u = l - 1;
            int v = r;

            if (componentId[u] != componentId[v]) {
                System.out.println("UNKNOWN");
            } else {
                // P[r] - P[l-1] = (dist[r] + base) - (dist[u] + base) = dist[r] - dist[u]
                System.out.println(dist[v] - dist[u]);
            }
        }
    }

    // DFS 预处理：从 node 出发，当前偏移为 currentDist，属于 compId 连通块
    private static void dfs(int node, long currentDist, int compId,
                            List<List<long[]>> graph, long[] dist,
                            boolean[] visited, int[] componentId) {
        visited[node] = true;
        dist[node] = currentDist;
        componentId[node] = compId;

        for (long[] edge : graph.get(node)) {
            int neighbor = (int) edge[0];
            long weight = edge[1];
            if (!visited[neighbor]) {
                dfs(neighbor, currentDist + weight, compId, graph, dist, visited, componentId);
            }
        }
    }
}

方法二：带权并查集

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();  // 数列长度
        int M = sc.nextInt();  // 已知部分和数量
        int Q = sc.nextInt();  // 查询数量

        // 初始化并查集（节点0~N，共N+1个节点）
        // parent[i]：i的父节点
        // weight[i]：prefix[i] - prefix[parent[i]]（i到父节点的差值）
        int[] parent = new int[N + 1];
        long[] weight = new long[N + 1];

        // 初始化：每个节点自成一个集合
        for (int i = 0; i <= N; i++) {
            parent[i] = i;  // 父节点指向自身
            weight[i] = 0;  // 到父节点的差值为0（prefix[i] - prefix[i] = 0）
        }

        // 处理M个已知部分和
        for (int i = 0; i < M; i++) {
            int l = sc.nextInt();  // 区间左端点
            int r = sc.nextInt();  // 区间右端点
            long S = sc.nextLong();  // 区间和

            // 转化为前缀和下标：prefix[l-1] 和 prefix[r]
            int u = l - 1;  // 对应前缀和下标l-1
            int v = r;      // 对应前缀和下标r

            // 查找u和v的根节点（同时进行路径压缩）
            int rootU = find(u, parent, weight);
            int rootV = find(v, parent, weight);

            // 如果不在同一集合，合并集合
            if (rootU != rootV) {
                // 合并rootU到rootV（rootU成为rootV的子节点）
                parent[rootU] = rootV;

                // 计算rootU到rootV的权重（关键公式）
                // 已知：prefix[v] - prefix[u] = S
                // 通过根节点关系：
                //   prefix[v] = prefix[rootV] + weight[v]
                //   prefix[u] = prefix[rootU] + weight[u]
                // 代入得：(prefix[rootV] + weight[v]) - (prefix[rootU] + weight[u]) = S
                // => prefix[rootU] = prefix[rootV] + weight[v] - weight[u] - S
                // 因此，rootU到rootV的权重为：weight[rootU] = prefix[rootU] - prefix[rootV] = weight[v] - weight[u] - S
                weight[rootU] = weight[v] - weight[u] - S;
            }
        }

        // 处理Q个查询
        for (int i = 0; i < Q; i++) {
            int l = sc.nextInt();  // 查询区间左端点
            int r = sc.nextInt();  // 查询区间右端点

            // 转化为前缀和下标：prefix[l-1] 和 prefix[r]
            int u = l - 1;
            int v = r;

            // 查找u和v的根节点（路径压缩后，weight[u]和weight[v]表示到根的差值）
            int rootU = find(u, parent, weight);
            int rootV = find(v, parent, weight);

            // 检查是否在同一集合
            if (rootU != rootV) {
                System.out.println("UNKNOWN");
            } else {
                // 区间和 = prefix[v] - prefix[u] = (prefix[root] + weight[v]) - (prefix[root] + weight[u]) = weight[v] - weight[u]
                System.out.println(weight[v] - weight[u]);
            }
        }
    }

    /**
     * 递归查找根节点（带路径压缩和权重更新）
     * @param x 当前节点
     * @param parent 父节点数组
     * @param weight 权重数组（存储到父节点的差值）
     * @return 根节点
     */
    private static int find(int x, int[] parent, long[] weight) {
        // 如果x不是根节点（x != parent[x]）
        if (x != parent[x]) {
            // 1. 递归找到x的父节点的根
            int root = find(parent[x], parent, weight);

            // 2. 更新x到根的距离：
            //    x到父节点的距离 + 父节点到根的距离 = x到根的距离
            weight[x] += weight[parent[x]];

            // 3. 路径压缩：x直接指向根
            parent[x] = root;
        }
        return parent[x];  // 返回根节点
    }
}