Problem: tile_transposing (2022 finals)

*Bejeweled*™ is a classic puzzle game where the player tries to match three-in-a-row in a 2D grid of tiles by swapping pairs of adjacent tiles.

*Isblinged*™ is Hacker Cup's spinoff, played on a grid of \(R\) rows by \(C\) columns of tiles. The tile at \((i, j)\) is of an integer type \(G_{i,j}\). A *group* refers to three or more tiles of the same type, connected directly or indirectly via the four orthogonal directions (left, right, up, and down). Initially, the given grid \(G\) may already contain groups.

The player may swap two orthogonally adjacent tiles *of different types*. If the swap results in either tile being in a group of three or more tiles, then all tiles in the *newly-formed group(s)* are cleared.

For the example below (sample case 2), swapping the first two tiles in row \(1\) would clear \(9\) tiles:

{{PHOTO_ID:1310493279783732|WIDTH:700}}

On the other hand, swapping the first two tiles in the second column would clear \(12\) tiles;

{{PHOTO_ID:650302073463012|WIDTH:700}}

Note that the type-3 group is not cleared because it doesn't contain a swapped tile.

Please find the *sum* of tiles that would be cleared over all possible theoretical swaps of ordered pairs of tiles \(G_{i_1, j_1}\) and \(G_{i_2, j_2}\) such that \(|i_1 - i_2| + |j_1 - j_2| = 1\) and \(G_{i_1, j_1} \ne G_{i_2, j_2}\).


# Constraints

\(1 \le T \le 105\)
\(1 \le R, C \le 3000\)
\(1 \le G_{i,j} \le 10^9\)

The sum of \(R*C\) across all test cases is at most \(40{,}000{,}000\).


# Input Format

Input begins with an integer \(T\), the number of cases. For each case, there is first a line containing two space-separated integers, \(R\) and \(C\). Then, \(R\) lines follow, the \(i\)th of which contains \(C\) space-separated integers \(G_{i,1..C}\).


# Output Format

For the \(i\)th case, print a line containing `"Case #i: "` followed by a single integer, the sum of tiles that can be cleared with a single swap.


# Sample Explanation

In the first sample case:
- \(G_{1,1}\), \(G_{1,3}\), and \(G_{2,3}\) can't be swapped with anything that leads to any tiles being cleared.
- \(G_{1,2}\) can be swapped with the type-2 tile below to clear \(3\) tiles.
- \(G_{2,1}\) can be swapped with the type-2 tile right of it to clear \(3\) tiles.
- \(G_{2,2}\) can be swapped with either the type-1 cell above or to the left, each clearing \(3\) tiles.

The answer is therefore \(3 + 3 + 2*3 = 12\).

In the second sample case, the unordered pairs of swaps clearing non-zero numbers of tiles are:
- \(G_{1,1} \leftrightarrow G_{1,2} \): clearing \(9\) tiles
- \(G_{1,2} \leftrightarrow G_{1,3} \): clearing \(5 + 3 = 8\) tiles
- \(G_{1,2} \leftrightarrow G_{2,1} \): clearing \(9 + 3 = 12\) tiles
- \(G_{1,3} \leftrightarrow G_{2,3} \): clearing \(5\) tiles
- \(G_{1,4} \leftrightarrow G_{2,4} \): clearing \(4\) tiles
- \(G_{2,2} \leftrightarrow G_{2,3} \): clearing \(6\) tiles
- \(G_{2,2} \leftrightarrow G_{3,2} \): clearing \(4\) tiles
- \(G_{2,4} \leftrightarrow G_{2,5} \): clearing \(4\) tiles
- \(G_{3,1} \leftrightarrow G_{3,2} \): clearing \(4\) tiles

Doubling the sum for ordered pairs, we get \(2*(9+8+12+5+4+6+4+4+4) = 112\).



Sample input:
3
2 3
1 1 2
1 2 3
3 5
1 2 1 1 1
1 1 2 2 1
1 3 3 3 1
4 4
1 1 1 4
1 2 1 1
3 2 3 4
3 2 2 2


Sample output:
Case #1: 12
Case #2: 112
Case #3: 74


Solution: Instead of swapping, first imagine shifting a tile \(G_{i,j}\) to replace an adjacent cell at \((i', j')\), leaving behind an empty space (instead of a different tile). Many things can happen:
- The tile itself can be disconnected from its old group.
- The tile can become connected to a new group.
- The tile, moving away, can break up its old group into multiple parts.
- The tile, at its new location, can merge different pre-existing groups into one.

Let \(C(i, j, i', j')\) denote the number of type-\(G_{i, j}\) tiles that will be connected to \((i', j')\) after shifting \(G_{i, j}\) to \((i', j')\). We can individually compute \(C(i, j, i', j') + C(i', j', i, j)\) to get the total number of tiles cleared in a single swap \(G_{i, j} \leftrightarrow G_{i',j'}\). The challenge is doing so efficiently.

We can build a graph with a node for each tile and an edge for every pair of adjacent tiles of the same type. There will be \(V = R*C \le 9{,}000{,}000\) nodes and \(E = O(4*R*C)\) edges. We could then theoretically solve the [dynamic connectivity](https://en.wikipedia.org/wiki/Dynamic_connectivity) problem to simulate adding/removing edges for each swap, and querying connected component sizes. Actually, we would only need to delete edges (decremental connectivity), query all neighbors of the new cell, and roll back the deletion using a persistent data structure. Unfortunately, even decremental connectivity is difficult to perform efficiently on general graphs.

Instead, we can try taking advantage of the structure of the graph. If we decompose the graph into [biconnected components](https://en.wikipedia.org/wiki/Biconnected_component) (BCCs), we see that the entire graph is a forest of block-cut trees (one for each tile group) connected by bridges at cut vertices (articulation points). For example, the cut vertices of the second sample case is denoted by asterisks:

```
1  2  1  1* 1*
1* 1  2  2  1*
1  3  3* 3  1
```

When we shift \(G_{i, j}\) to a neighboring cell \((i', j')\), there are two cases:

_Case 1_: Tile \(G_{i, j}\) was not a cut vertex: All tiles of the original group will remain connected, except maybe the shifted tile itself. Then, \(C(i, j, i', j')\) can be computed by summing the sizes of groups of type \(G_{i,j}\) that are connected to \((i', j')\). Note that neighbors can be in the same group as each other, or in \(G_{i, j}\)'s original group. We'll need a way to check the connectness of two arbitrary nodes to avoid double counting.

_Case 2_: Tile \(G_{i, j}\) was a cut vertex: We'll need a way to temporarily disconnect it before calculating the group sizes connected to \((i', j')\). The number of edges for the cut vertex (a.k.a. its color) can only be \(2\) or \(3\), for if all \(4\) neighbors were filled, the swap wouldn't be possible.

\(2\)-colored cut vertex examples:
```
1 1* 1     1 1*
             1* 1
```
\(3\)-colored cut vertex example:
```
  1 1
1 1*
  1 1
```

In the above cases, each cut vertex is always in its own BCC block, so disconnecting the node is the same as disconnecting the entire block in the block forest.

Working through examples by hand, we see that the only way for a cut vertex to *not* be in its own size-\(1\) block is as follows (left). We have a \(2\)-colored cut vertex but its block is the entire loop:
```
  1 1 1 1 1           1 1 1 1 1          1 1 1 1 1
  1       1           1       1          1   1   1
1 1* ...  1   -->   1   1 1   1   or   1   1 1   1
  1       1           1       1          1       1
  1 1 1 1 1           1 1 1 1 1          1 1 1 1 1
```

In this case, the shifted tile may become connected to a different group (middle), or to its own group again (right). Here, we can skip the disconnection/rolling back and just get the total group sizes of the other \(3\) neighbors of \((i', j')\). We'll only add \(1\) if the tile did not get reconnected to its original group.

With these observations, we can obtain the answer by solving dynamic connectivity on the block forest. For each condensed block node, we'll store the number of actual nodes in the block, a.k.a. the block size. We'll need to efficiently:

- delete an edge (and undo the deletion)
- check connectivity
- query an aggregate function (here, the sum of BCC block sizes) for an entire block tree

One way is with a link-cut forest modified to handle [subtree aggregates](https://usaco.guide/adv/link-cut-tree?lang=cpp#link-cut-tree---subtrees) (full tree queries are just a special case), which can be done with [virtual subtrees](https://codeforces.com/blog/entry/67637#comment-650436). This was the intended solution, and directly supports all of the operations we need. Other approaches include persistent disjoint set union, DFS, and bookkeeping of node component sizes.

Biconnected components and cut vertices can be computed in \(\mathcal{O}(V + E)\) time using Tarjan's algorithm. For each \(C(i, j, i', j')\) calculation, we'll do a constant number of cuts, connectivity checks, and queries on the link-cut forest, taking \(\mathcal{O}(\log V)\) time among them. The overall time complexity to compute the answer across all possible swaps is therefore \(\mathcal{O}(E + V \log V)\).


Code: #include <algorithm>
#include <cstring>
#include <iostream>
#include <stack>
#include <tuple>
#include <unordered_set>
#include <vector>
using namespace std;

const int LIM = 3005;
const int MAXN = LIM * LIM;

vector<int> adj[MAXN];
unordered_set<int> cutpoints;
vector<int> comp;
vector<vector<int>> bcc, bcc_adj;

void reset_edges() {
  for (int i = 0; i < MAXN; i++) {
    adj[i].clear();
  }
}

void add_edge(int u, int v) {
  adj[u].push_back(v);
  adj[v].push_back(u);
}

void tarjan(int N) {
  cutpoints.clear();
  bcc.clear();
  comp.assign(N, -1);
  vector<int> vis(N), parent(N, -1), children(N), tin(N), pushed(N), low(N);
  vector<bool> is_cut(N);
  int curr_root = 0;
  stack<tuple<int, int, int>> dfs;
  stack<int> st;
  for (int i = 0; i < N; i++) {
    if (vis[i]) {
      continue;
    }
    vis[i] = ++curr_root;
    tin[i] = 0;
    int timer = 1;
    dfs.push({i, 0, 0});
    while (!dfs.empty()) {
      auto [u, j, t] = dfs.top();
      low[u] = t;
      if (!pushed[u]) {
        st.push(u);
        pushed[u] = 1;
      }
      if (j == (int)adj[u].size()) {
        if ((parent[u] == -1 && children[u] >= 2) ||
            (parent[u] != -1 && is_cut[u])) {
          cutpoints.insert(u);
        }
        if (t >= tin[u]) {
          vector<int> component;
          do {
            int v = st.top();
            component.push_back(v);
            comp[v] = bcc.size();
            st.pop();
          } while (comp[u] == -1);
          bcc.push_back(component);
        }
        dfs.pop();
        continue;
      }
      int v = adj[u][j];
      if (parent[u] == v) {
        get<1>(dfs.top())++;
        continue;
      }
      if (vis[v] == 0) {
        vis[v] = curr_root;
        parent[v] = u;
        children[u]++;
        dfs.push({v, 0, timer});
        tin[v] = timer++;
        continue;
      }
      is_cut[u] = is_cut[u] || low[v] >= tin[u];
      if (vis[v] == curr_root && comp[v] == -1 && low[v] < t) {
        get<2>(dfs.top()) = low[v];
      }
      get<1>(dfs.top())++;
    }
  }
  bcc_adj.assign(bcc.size(), {});
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < (int)adj[i].size(); j++) {
      if (comp[i] != comp[adj[i][j]]) {
        bcc_adj[comp[i]].push_back(comp[adj[i][j]]);
      }
    }
  }
}

template <class Value>
class LinkCut {
  struct Node {
    int ch[2] = {0, 0}, p = 0;
    Value self = 0, path = 0;  // Path aggregates
    Value sub = 0, vir = 0;    // Subtree aggregates
    bool flip = 0;             // Lazy tags
  };

  vector<Node> T;

  void push(int x) {
    if (x == 0 || !T[x].flip) {
      return;
    }
    int l = T[x].ch[0], r = T[x].ch[1];
    T[l].flip ^= 1;
    T[r].flip ^= 1;
    swap(T[x].ch[0], T[x].ch[1]);
    T[x].flip = 0;
  }

  void pull(int x) {
    int l = T[x].ch[0], r = T[x].ch[1];
    push(l);
    push(r);
    T[x].path = T[l].path + T[x].self + T[r].path;
    T[x].sub = T[x].vir + T[l].sub + T[r].sub + T[x].self;
  }

  void set(int x, int d, int y) {
    T[x].ch[d] = y;
    T[y].p = x;
    pull(x);
  }

  void splay(int x) {
    auto dir = [&](int x) {
      int p = T[x].p;
      if (p == 0) {
        return -1;
      }
      return T[p].ch[0] == x ? 0 : T[p].ch[1] == x ? 1 : -1;
    };
    auto rotate = [&](int x) {
      int y = T[x].p, z = T[y].p, dx = dir(x), dy = dir(y);
      set(y, dx, T[x].ch[!dx]);
      set(x, !dx, y);
      if (~dy) {
        set(z, dy, x);
      }
      T[x].p = z;
    };
    for (push(x); ~dir(x);) {
      int y = T[x].p, z = T[y].p;
      push(z);
      push(y);
      push(x);
      int dx = dir(x), dy = dir(y);
      if (~dy) {
        rotate(dx != dy ? x : y);
      }
      rotate(x);
    }
  }

  int access(int x) {
    int v = 0;
    for (int u = x; u != 0; u = T[u].p) {
      splay(u);
      int &ov = T[u].ch[1];
      T[u].vir += T[ov].sub;
      T[u].vir -= T[v].sub;
      ov = v;
      pull(u);
      v = u;
    }
    splay(x);
    return v;
  }

  void reroot(int x) {
    access(x);
    T[x].flip ^= 1;
    push(x);
  }

 public:
  LinkCut(int n = 0) : T(n + 1) {}

  void Init(int u, Value v) {
    T[++u].self = v;
    pull(u);
  }

  void Reset(int n) {
    T.clear();
    T.resize(n + 1);
  }

  void Link(int u, int v) {
    if (u == v || LCA(u, v) != -1) {
      return;
    }
    reroot(++u);
    access(++v);
    T[v].vir += T[u].sub;
    T[u].p = v;
    pull(v);
  }

  void Cut(int u, int v) {
    if (u == v || LCA(u, v) == -1) {
      return;
    }
    reroot(++u);
    access(++v);
    T[v].ch[0] = T[u].p = 0;
    pull(v);
  }

  // Rooted tree LCA. Returns -1 if u and v aren't connected.
  int LCA(int u, int v) {
    if (++u == ++v) {
      return u;
    }
    access(u);
    int ret = access(v);
    return T[u].p ? ret : -1;
  }

  // Query subtree of u where v is outside the subtree.
  // Pass u = v to get the aggregate for the entire tree containing u.
  Value Subtree(int u, int v) {
    reroot(++v);
    access(++u);
    return T[u].vir + T[u].self;
  }

  Value Path(int u, int v) {
    reroot(++u);
    access(++v);
    return T[v].path;
  }

  void Update(int u, Value v) {
    access(++u);
    T[u].self = v;
    pull(u);
  }
};

// Main algorithm.

int R, C;
int G[LIM][LIM];
LinkCut<int> lcf;

inline int getn(int r, int c) { return r * C + c; }
inline int getr(int n) { return n / C; }
inline int getc(int n) { return n % C; }

// Size of group connected to (r2, c2) after swapping (r1, c1) to (r2, c2).
int num_cleared(int r1, int c1, int r2, int c2) {
  int res = 0;
  int u = getn(r1, c1), cu = comp[u];
  // If u is a cutpoint, disconnect it from all neighboring BCCs.
  if (cutpoints.count(u)) {
    for (int v : adj[u]) {
      int cv = comp[v];
      if (cu != cv) {
        lcf.Cut(cu, cv);
      }
    }
  }
  // Get a representative for each neighboring group of (r2, c2).
  unordered_set<int> seen_groups;
  bool seen_orig = false;  // Whether we've seen the original group of cu.
  for (auto [dr, dc] : {pair{-1, 0}, {0, 1}, {1, 0}, {0, -1}}) {
    int r3 = r2 + dr, c3 = c2 + dc;
    if (r3 < 0 || r3 >= R || c3 < 0 || c3 >= C) {
      continue;
    }
    if (!(r1 == r3 && c1 == c3) && G[r1][c1] == G[r3][c3]) {
      int cv = comp[getn(r3, c3)];
      bool seen = false;  // Have we seen the same group?
      for (int cmp : seen_groups) {
        if (lcf.LCA(cv, cmp) != -1) {
          seen = true;
          break;
        }
      }
      if (!seen) {
        if (lcf.LCA(cu, cv) != -1) {
          seen_orig = true;
        }
        res += lcf.Subtree(cv, cv);
        seen_groups.insert(cv);
      }
    }
  }
  // If we didn't encounter the original component, add 1 for the cell itself.
  if (!seen_orig) {
    res++;
  }
  // Undo disconnections.
  if (cutpoints.count(u)) {
    for (int v : adj[u]) {
      int cv = comp[v];
      if (cu != cv) {
        lcf.Link(cu, cv);
      }
    }
  }
  return res >= 3 ? res : 0;
}

long long solve() {
  reset_edges();
  // Build graph.
  for (int r = 0; r < R; r++) {
    for (int c = 0; c < C; c++) {
      for (auto [dr, dc] : {pair{0, 1}, {1, 0}}) {
        int r2 = r + dr, c2 = c + dc;
        if (r2 < 0 || r2 >= R || c2 < 0 || c2 >= C) {
          continue;
        }
        if (G[r][c] == G[r2][c2]) {
          add_edge(getn(r, c), getn(r2, c2));
        }
      }
    }
  }
  // Compute BCC and block forest.
  tarjan(R * C);
  int bcc_nodes = (int)bcc.size();
  // Create link-cut forest from BCC.
  lcf.Reset(bcc_nodes);
  for (int i = 0; i < bcc_nodes; i++) {
    lcf.Init(i, bcc[i].size());
  }
  for (int i = 0; i < bcc_nodes; i++) {
    for (int j : bcc_adj[i]) {
      lcf.Link(i, j);
    }
  }
  // Try swapping each neighbor.
  long long ans = 0;
  for (int r = 0; r < R; r++) {
    for (int c = 0; c < C; c++) {
      // Only check right and bottom for ordered pairs.
      for (auto [dr, dc] : {pair{0, 1}, {1, 0}}) {
        int r2 = r + dr, c2 = c + dc;
        if (r2 < 0 || r2 >= R || c2 < 0 || c2 >= C) {
          continue;
        }
        if (G[r][c] != G[r2][c2]) {
          ans += num_cleared(r, c, r2, c2) + num_cleared(r2, c2, r, c);
        }
      }
    }
  }
  return 2 * ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    memset(G, 0, sizeof G);
    cin >> R >> C;
    for (int r = 0; r < R; r++) {
      for (int c = 0; c < C; c++) {
        cin >> G[r][c];
      }
    }
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}