什么是离线操作，与有线操作有什么区别？
离线操作指一次读入所有操作后再处理，可以顺序处理，可以倒序处理，也可以按任意顺序处理。
而有线操作指根据输入，来一个处理一个，只能按照输入顺序处理。

803. 打砖块

有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：

  • 一块砖直接连接到网格的顶部，或者
  • 至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时

给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。
返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。
注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。

示例 1：
输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]] 输出：[2] 解释： 网格开始为： [[1,0,0,0]， [1,1,1,0]] 消除 (1,0) 处加粗的砖块，得到网格： [[1,0,0,0] [0,1,1,0]] 两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格： [[1,0,0,0], [0,0,0,0]] 因此，结果为 [2] 。
示例 2：
输入：grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]] 输出：[0,0] 解释： 网格开始为： [[1,0,0,0], [1,1,0,0]] 消除 (1,1) 处加粗的砖块，得到网格： [[1,0,0,0], [1,0,0,0]] 剩下的砖都很稳定，所以不会掉落。网格保持不变： [[1,0,0,0], [1,0,0,0]] 接下来消除 (1,0) 处加粗的砖块，得到网格： [[1,0,0,0], [0,0,0,0]] 剩下的砖块仍然是稳定的，所以不会有砖块掉落。 因此，结果为 [0,0] 。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • grid[i][j] 为 0 或 1
  • 1 <= hits.length <= 4 * 104
  • hits[i].length == 2
  • 0 <= xi <= m - 1
  • 0 <= yi <= n - 1
  • 所有 (xi, yi) 互不相同

思路：
正向处理不好办，因为并查集没有说一个点离开并查集后哪些点会跟着离开，但是并查集支持集合合并操作，同时能知道新加入多少个节点。因此可以采用离线操作，读取所有输入后，遍历一遍待操作位置，记录所有应该做操作的位置并将该位置砖块消掉。
用一个超级源点表示不会掉落的砖块。遍历一遍所有砖块，进行并查集合并操作。
反向处理所有待处理操作，将对应位置的砖块加回来，看看能超级源点所在集合会新增多少砖块，就剩原本击落它会掉落的砖块数。

  1. class Solution {
  2.     int n, m;
  3.     int[] fa, size;
  4.     int get(int x, int y) {
  5.         return x * m + y;
  6.     }
  7.     int find(int x) {
  8.         return x == fa[x] ? x : (fa[x] = find(fa[x]));
  9.     }
  10.     void merge(int x, int y) {
  11.         int px = find(x), py = find(y);
  12.         if (px == py) return;
  13.         fa[px] = py;
  14.         size[py] += size[px];
  15.     }
  16.     public int[] hitBricks(int[][] grid, int[][] hits) {
  17.         n = grid.length;
  18.         m = grid[0].length;
  19.         int S = n * m;
  20.         fa = new int[S + 1];
  21.         size = new int[S + 1];
  22.         for (int i = 0; i <= S; i++) {
  23.             fa[i] = i;
  24.             size[i] = 1;
  25.         }
  27.         int len = hits.length;
  28.         boolean[] st = new boolean[len];
  29.         for (int i = 0; i < len; i++) {
  30.             int x = hits[i][0], y = hits[i][1];
  31.             if (grid[x][y] == 1) {
  32.                 grid[x][y] = 0;
  33.                 st[i] = true;
  34.             }
  35.         }
  37.         int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
  38.         for (int i = 0; i < n; i++) {
  39.             for (int j = 0; j < m; j++) {
  40.                 if (grid[i][j] == 0) continue;
  41.                 int a = get(i, j);
  42.                 if (i == 0)
  43.                     merge(a, S);
  45.                 for (int k = 0; k < 4; k++) {
  46.                     int c = i + dx[k], d = j + dy[k];
  47.                     int b = get(c, d);
  48.                     if (c >= 0 && c < n && d >= 0 && d < m && grid[c][d] == 1) {
  49.                         merge(a, b);
  50.                     }
  51.                 }
  52.             }
  53.         }
  55.         int[] res = new int[len];
  56.         int last = size[find(S)];
  58.         for (int i = len - 1; i >= 0; i--) {
  59.             if (st[i]) {
  60.                 int x = hits[i][0], y = hits[i][1];
  61.                 grid[x][y] = 1;
  62.                 int a = get(x, y);
  63.                 if (x == 0)
  64.                     merge(a, S);
  66.                 for (int j = 0; j < 4; j++) {
  67.                     int c = x + dx[j], d = y + dy[j];
  68.                     int b = get(c, d);
  69.                     if (c >= 0 && c < n && d >= 0 && d < m && grid[c][d] == 1) {
  70.                         merge(a, b);
  71.                     }
  72.                 }
  73.             }
  74.             res[i] = Math.max(0, size[find(S)] - last - 1);
  75.             last = size[find(S)];
  76.         }
  77.         return res;
  78.     }
  79. }
  1. // 方法2  并查集改为深搜，速度更快
  2. class Solution {
  3.     int n, m;
  4.     public int[] hitBricks(int[][] grid, int[][] hits) {
  5.         for (int[] p : hits) {
  6.             int x = p[0], y = p[1];
  7.             grid[x][y]--;
  8.         }
  9.         n = grid.length; 
  10.         m = grid[0].length;
  11.         for (int i = 0; i < m; i++) {
  12.             if (grid[0][i] == 1) {
  13.                 dfs(0, i, grid);
  14.             }
  15.         }
  17.         int len = hits.length;
  18.         int[] res = new int[len];
  19.         for (int i = len - 1; i >= 0; i--) {
  20.             int x = hits[i][0], y = hits[i][1];
  21.             grid[x][y]++;
  22.             if (grid[x][y] <= 0) {
  23.                 continue;
  24.             }
  25.             boolean flag = false;
  26.             if (x == 0) flag = true;
  27.             for (int j = 0; j < 4; j++) {
  28.                 int a = x + dx[j], b = y + dy[j];
  29.                 if (a >= 0 && a < n && b >= 0 && b < m && grid[a][b] >= 2)
  30.                     flag = true;
  31.             }
  32.             if (flag)
  33.                 res[i] = dfs(x, y, grid) - 1;
  34.         }
  35.         return res;
  36.     }
  38.     int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
  39.     int dfs(int x, int y, int[][] grid) {
  40.         grid[x][y]++;
  41.         int cnt = 0;
  42.         for (int i = 0; i < 4; i++) {
  43.             int a = x + dx[i], b = y + dy[i];
  44.             if (a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == 1)
  45.                 cnt += dfs(a, b, grid);
  46.         }
  47.         return cnt + 1;
  48.     }
  49. }

1938. 查询最大基因差
小美的仓库整理
小美是美团仓库的管理员，她会根据单据的要求按顺序取出仓库中的货物，每取出一件货物后会把剩余货物重新堆放，使得自己方便查找。已知货物入库的时候是按顺序堆放在一起的。如果小美取出其中一件货物，则会把货物所在的一堆物品以取出的货物为界分成两堆，这样可以保证货物局部的顺序不变。
已知货物最初是按 1~n 的顺序堆放的，每件货物的重量为 w[i] ,小美会根据单据依次不放回的取出货物。请问根据上述操作，小美每取出一件货物之后，重量和最大的一堆货物重量是多少？

输入：
- 输入第一行包含一个正整数 n ，表示货物的数量。
- 输入第二行包含 n 个正整数，表示 1~n 号货物的重量 w[i] 。
- 输入第三行有 n 个数，表示小美按顺序取出的货物的编号，也就是一个 1~n 的全排列。
输出：
- 输出包含 n 行，每行一个整数，表示每取出一件货物以后，对于重量和最大的一堆货物，其重量和为多少。
示例：
输入：
5
3 2 4 4 5
4 3 5 2 1
输出：
9
5
5
3
0
解释：
原本的状态是 {{3,2,4,4,5}} ，取出 4 号货物后，得到 {{3,2,4},{5}} ，第一堆货物的和是 9 ，然后取出 3 号货物得到 {{3,2}{5}} ，此时第一堆和第二堆的和都是 5 ，以此类推。
提示：
1 <= n <= 50000
1 <= w[i] <= 100

思路：倒着处理，把拿走变为添加，用并查集处理连通块的最大质量。

  1. import java.util.*;
  2. public class Main {
  3.     public static void main(String[] args) {
  4.         Scanner sc = new Scanner(System.in);
  6.         int n = sc.nextInt();
  7.         int[] a = new int[n + 1];
  8.         for (int i = 1; i <= n; i++)
  9.             a[i] = sc.nextInt();
  10.         int[] op = new int[n + 1];
  11.         for (int i = 1; i <= n; i++)
  12.             op[i] = sc.nextInt();
  14.         UnionFind uf = new UnionFind(n + 1);
  15.         int[] res = new int[n + 1];
  16.         for (int i = n; i >= 1; i--) {
  17.             res[i] = uf.max;
  18.             uf.merge(op[i], a[op[i]]);
  19.         }
  20.         for (int i = 1; i <= n; i++)
  21.             System.out.println(res[i]);
  23.     }
  24. }
  25. class UnionFind{
  26.     int[] fa;
  27.     int[] size;
  28.     int n, max;
  29.     UnionFind(int n) {
  30.         this.n = n;
  31.         fa = new int[n];
  32.         size = new int[n];
  33.         for (int i = 0; i < n; i++)
  34.             fa[i] = i;
  35.     }
  37.     int find(int x) {
  38.         return x == fa[x] ? x : (fa[x] = find(fa[x]));
  39.     }
  40.     void merge(int idx, int x) {
  41.         size[idx] = x;
  42.         if (size[idx - 1] > 0) {
  43.             int p = find(idx - 1);
  44.             size[p] += size[find(idx)];
  45.             fa[find(idx)] = p;
  46.         }
  47.         if (idx + 1 < n && size[idx + 1] > 0) {
  48.             int p = find(idx + 1);
  49.             size[p] += size[find(idx)];
  50.             fa[find(idx)] = p;
  51.         }
  52.         max = Math.max(size[find(idx)], max);
  53.     }
  54. }