Problem: expl-ore-ation_ch3 (2021 round3)

**Note: Chapters [1](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-3/problems/D1) and [2](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-3/problems/D2) are strictly less difficult versions of this problem, with differences in bold. Solutions to later chapters can be directly applied to solve earlier ones.**

Facebulk Inc. is a mining company who just released its latest performance reports. Backed by strong earnings, the company is now seeking to grow its infrastructure by surveying ore samples across \(T\) new sites using its patented robotics tech.

A given site has been excavated after much drilling and blasting, forming a rectangular pit that's \(R\) rows long (numbered from \(1\) to \(R\)) by \(C\) columns wide (numbered from \(1\) to \(C\)) by \(10^9\) cm deep. The pit consists of a grid of \(R*C\) platforms, where the platform at row \(i\) and column \(j\) (denoted as platform \((i, j)\)) is at height \(H_{i,j}\) cm from the bottom of the pit.

Unfortunately, there's a forecast of heavy rain — rainwater is about to start slowly flooding the pit. The water level is initially at height \(0\), and will eventually fill up the entire pit at height \(10^9\) cm.

Your supervisor wants \(R*C\) ore samples to be collected and analyzed, one from each platform, based on the following humidity requirements: the sample from platform \((i, j)\) is *only* worthwhile if collected at some point while the water level is strictly between \(S_{i,j}\) and \(S_{i,j}+1\) cm.

In an attempt to accomplish this, you'll dispatch \(0\) or more remote-control robots before it starts to rain, each at an initial platform of your choice. Multiple robots may occupy the same platform. At any point in time, you can command any robot at some platform \((i, j)\) to move to an adjacent platform (any platform \((i', j')\) such that \(|i-i'| + |j-j'| = 1\)), or to collect an ore sample from its current platform. Rainwater will flood slowly enough that the robots have time to execute an arbitrary number of commands before water increases from any height of \(x\) to \(x+1\) cm.

If a robot is ever on platform \((i, j)\) while the water level is greater than or equal to \(H_{i,j}\) (either because the robot moved to that platform or because the water level increased while the robot was present on it), the robot will short circuit and stop executing any more commands.

**To make matters more complicated, before you get to start implementing any plan, your supervisor will keep changing their mind about what samples are worthwhile.** They'll change their mind \(K\) times, such that the \(i\)th time, they'll decide that \(S_{A_i,B_i}\) will henceforth actually be equal to \(U_i\) (until they potentially change their mind about it again).

Considering the situation after your supervisor has changed their mind the first \(i\) times, let \(X_i\) be the maximum number of desired ore samples which could theoretically be collected, and let \(Y_i\) be the minimum number of robots which must theoretically be dispatched to collect that many samples. Please compute the sum of \(X_{1..K}\) and the sum of \(Y_{1..K}\).

**Your supervisor insists that you finish assessing the \(i\)th situation and computing \(X_i\) and \(Y_i\) before they tell you how they've changed their mind for the \((i+1)\)th time.** To that end, you will not be given \(A_{1..K}\), \(B_{1..K}\), and \(U_{1..K}\) directly; you'll instead be given different sequences of values \(A'_{1..K}\), \(B'_{1..K}\), and \(U'_{1..K}\). 

Given \(A_1 = A'_1\), \(B_1 = B'_1\), and \(U_1 = U'_1\), for each \(i \ge 2\) you must compute \(A_i = A'_i \oplus Y_{i-1}\), \(B_i = B'_i \oplus Y_{i-1}\), and \(U_i = U'_i \oplus Y_{i-1}\) for yourself (where \(\oplus\) is the bitwise xor operator, `'^'` in many programming languages).

# Constraints

\(1 \le T \le 45\)
\(1 \le R, C \le 1{,}000{,}000\)
\(R*C \le 1{,}000{,}000\)
\(1 \le H_{i,j} \le 1{,}000{,}000{,}000\)
\(0 \le S_{i,j} < 1{,}000{,}000{,}000\)
\(1 \le K \le 1{,}000{,}000\)
\(1 \le A_i \le R\)
\(1 \le B_i \le C\)
\(0 \le U_i < 1{,}000{,}000{,}000\)
\(0 \le A'_i, B'_i, U'_i \le 2{,}000{,}000{,}000\)

The sum of \(R*C + K\) across all sites is at most \(5{,}000{,}000\).


# Input

Input begins with an integer \(T\), the number of sites to be surveyed. For each site, there is first a line containing \(2\) space-separated integers, \(R\) and \(C\). Then, \(R\) lines follow, the \(i\)th of which consists of \(C\) space-separated integers, \(H_{i,1..C}\). Then, another \(R\) lines follow, the \(i\)th of which consists of \(C\) space-separated integers \(S_{i,1..C}\). Then, a line will follow containing the single integer \(K\). Then, \(K\) lines will follow, the \(i\)th of which contains \(3\) space-separated integers, \(A'_i\), \(B'_i\), and \(U'_i\).


# Output

For the \(i\)th site, print a line containing *"Case #i: "* followed by \(2\) space-separated integers, the sum of \(X_{1..K}\), and the sum of \(Y_{1..K}\).


# Sample Explanation

At the first site, \(S_{1,1}\) will immediately get changed to \(98\). If you were to then dispatch a single robot at platform \((1, 2)\), it could wait there until the water level exceeds \(98\) cm, collect an ore sample from platform \((1, 2)\), move to platform \((1, 3)\), wait until the water level exceeds \(99\) cm, and finally collect an ore sample from platform \((1, 3)\). No matter how many robots were to be dispatched, they could not collect an ore sample from platform \((1, 1)\) after the water level exceeds \(98\) cm (as the platform would already be flooded), meaning that \(1\) robot collecting \(2\) samples is the best that can be done. Therefore, \(X = [2]\) and \(Y = [1]\).

At the second site, once \(S_{1,1}\) gets changed to \(5\), the ore sample at platform \((1, 1)\) would be possible to collect (by a single robot). Therefore \(X_1 = Y_1 = 1\). In turn, \(A_2 = 0 \oplus 1 = 1\), \(B_2 = 0 \oplus 1 = 1\), and \(U_2 = 14 \oplus 1 = 15\). Once \(S_{1,1}\) gets changed to \(15\), the ore sample would no longer be possible to collect. Therefore, \(X_2 = Y_2 = 0\), and so \(A_3 = 1 \oplus 0 = 1\), \(B_3 = 1 \oplus 0 = 1\), and \(U_3 = 5 \oplus 0 = 5\). Once it gets changed back to \(5\), the sample would once again be possible to collect. Therefore, \(X_3 = Y_3 = 1\), and the sums of \(X_{1..K}\) and of \(Y_{1..K}\) are both equal to \(2\).

At the third site, a single robot dispatched anywhere would be able to move around and collect samples from all 6 platforms before the water level reaches \(1\) cm — therefore, \(X = [6]\) and \(Y = [1]\).

At the fourth site, no samples can be collected before all \(6\) platforms get flooded — therefore, \(X = [0]\) and \(Y = [0]\).

At the fifth site, once \(S_{1,2}\) gets changed to \(2\), samples at platforms \((1, 1)\) and \((1, 3)\) would be possible to be collect, though not by a single robot — therefore, \(X_1 = 2\) and \(Y_1 = 2\). Overall, \(X = [2, 2, 3, 3, 4]\) and \(Y = [2, 1, 1, 1, 2]\), with \(A = [1, 1, 2, 1, 2]\), \(B = [2, 1, 2, 3, 1]\), and \(U = [2, 1, 1, 2, 2]\).

At the sixth site:
- \(X = [68, 67, 66, 67, 67, 66, 65, 65, 64, 65]\)
- \(Y = [12, 12, 12, 12, 12, 11, 11, 11, 10, 10]\)
- \(A = [3, 1, 2, 3, 4, 4, 4, 3, 4, 3]\)
- \(B = [17, 18, 10, 4, 4, 20, 7, 13, 8, 18]\)
- \(U = [17, 69, 64, 12, 17, 100, 84, 20, 42, 53]\)

*Note: These sample cases represent the same data as those in [Chapter 2](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-3/problems/D2), just in a different format.*


Sample input:
6
1 3
98 99 100
97 98 99
1
1 1 98
1 1
10
10
3
1 1 5
0 0 14
1 1 5
2 3
5 2 4
3 2 1
0 0 0
0 0 0
1
1 1 0
2 3
5 2 4
3 2 1
5 5 5
5 5 5
1
2 3 5
2 3
5 2 4
3 2 1
3 3 3
3 3 3
5
1 2 2
3 3 3
3 3 0
0 2 3
3 0 3
4 20
68 31 93 93 46 61 8 11 98 56 26 53 72 52 92 67 75 67 67 99
52 96 82 18 23 6 36 69 8 62 54 79 53 6 46 3 17 21 79 95
42 7 61 13 24 93 4 2 45 61 82 33 26 53 55 9 24 86 69 47
85 70 58 67 65 7 84 22 3 47 72 82 34 99 94 98 2 1 45 100
63 15 75 72 44 34 57 10 30 43 20 49 66 45 66 0 76 66 62 96
44 67 61 15 22 41 33 68 5 44 43 70 52 3 43 3 11 16 77 71
74 6 45 19 25 50 90 2 38 52 58 29 24 31 52 5 16 88 39 29
78 67 55 51 39 70 76 18 3 3 66 12 31 71 71 88 1 0 39 91
10
3 17 17
13 30 73
14 6 76
15 8 0
8 8 29
8 24 104
15 12 95
8 6 31
15 3 33
9 24 63


Sample output:
Case #1: 2 1
Case #2: 2 2
Case #3: 6 1
Case #4: 0 0
Case #5: 14 7
Case #6: 660 113


Solution: Similarly to Chapters 1 and 2, we'll simulate the flooding process in reverse, processing events for adjacent platforms becoming reachable while maintaining a disjoint-set data structure of mutually-reachable groups of platforms. The big difference is that sample collection events can no longer also be processed along the way — each of the \(K\) updated \(S\) values will need to be processed separately. Each can be thought of as a removal of an existing S value followed by an insertion of a new \(S\) value (at which point, the initial \(RC\) \(S\) values might as well be inserted in the same way).

While simulating the flooding process, we'll construct a corresponding binary tree. Each initial group in the disjoint-set data structure will correspond to a leaf node, and whenever two groups get merged, their corresponding tree nodes will become the children of the resulting group's new tree node, with the tree's root being the node corresponding to the single final group consisting of all \(RC\) platforms. Each tree node will be relevant to a certain interval of heights (dictated by the heights of the events which caused the node to be created and to become another node's child), which will be stored as well.

Now, for a given rock sample (to be collected at a certain platform while the water level is at a certain height), we can think of the tree node which "contains" that sample as the highest ancestor of that platform's corresponding leaf node whose relevant height interval includes that height. As we go, we'll maintain information about which tree nodes currently contain collectable samples (of which there are at most \(RC\) at any point in time). In this representation, each robot is capable of collecting all samples contained in nodes along a single path from the root to a leaf node. This makes it reasonable to determine the minimum number of robots \(y\) required to collect all current samples, and to update this quantity as samples get inserted or removed.

When a sample is about to get inserted at node \(i\), it can either cause \(y\) to increase by \(1\) or remain unchanged. If there are any other samples in node \(i\)'s subtree, then \(y\) must remain unchanged, as a robot handling such a sample could also handle the new sample along the way. Otherwise, let \(a\) be node \(i\)'s closest ancestor containing any samples (if any). If there's no such ancestor \(a\), then \(y\) must increase by \(1\), as there are no other samples which an existing robot could be handling before or after the new sample. Otherwise, \(y\) must increase by \(1\) if and only if there are no other samples amongst node \(a\)'s descendants — if there are, then the robot handling node \(a\)'s samples must already be tied up with handling another existing sample, while if there aren't, then that robot can come handle the new sample.

When a sample gets removed, essentially identical logic can be applied to determine whether \(y\) should decrease by \(1\) or remain unchanged.

What remains is implementing all of the pieces described above efficiently, which can be accomplished with a variety of relatively standard tree algorithms:

  - To find the tree node which contains a given sample, we can start by precomputing a list of the 1st, 2nd, 4th, 8th, etc. ancestors of each node in \(O(RC \log(RC))\) time. Starting at the relevant platform's leaf node, we can then perform \(O(\log(RC))\) jumps up these lists (based on nodes' relevant height intervals) to arrive at the appropriate node.
  - To determine whether or not a subtree contains any samples, we can start by traversing the tree in pre-order and precomputing each node's subtree's interval of pre-order indices in \(O(RC)\) time. Assuming we maintain a multiset of pre-order indices of nodes containing samples, we can then query whether this multiset contains elements in appropriate intervals. Each multiset insertion, deletion, and query takes \(O(\log(RC))\) time.
  - To find a node's closest ancestor containing any samples, we can start by performing a [heavy-light decomposition](https://en.wikipedia.org/wiki/Heavy_path_decomposition) of the tree in \(O(RC)\) time. Assuming we similarly maintain a multiset of indices of nodes containing samples on each heavy path (also possible to implement as a single multiset reused across all heavy paths), we can then traverse individual nodes and heavy paths upwards from a given node while querying their multisets for the earliest relevant element. Each multiset insertion, deletion, and query takes \(O(\log(RC))\) time, and \(O(\log(RC))\) queries might be performed each time. A slightly faster but more complicated approach is to use splay trees with preferred paths in the same style as link-cut trees instead of HLD, which allows us to save a \(\log(RC)\) factor.

The time complexity of this algorithm comes out to \(O((RC+K) \log^2(RC))\), or just \(O((RC+K)\log(RC))\) if implemented with splay trees.


[See David Harmeyer (SecondThread)'s solution video here.](https://youtu.be/w6Xvy0c876o?t=524)


Code: #include <algorithm>
#include <cstring>
#include <iostream>
#include <set>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

const int INF = 1000000000;
const int LIM = 1000002;
const int LIM2 = 2000002;
const int LIM3 = 23;

int R, C, N, K;
int H[LIM], S[LIM];
vector<tuple<int, int, int>> A;
pair<int, int> curr;
int M;
int children[LIM2][2];
int parent[LIM2][LIM3];
int high[LIM2];

struct UnionFind {
  int N;
  vector<int> root, rank, node;

  UnionFind(int _N) : N(_N), root(_N), rank(_N, 0), node(_N) {
    for (int i = 0; i < N; i++) {
      root[i] = i;
      node[i] = M;
      children[M][0] = children[M][1] = -1;
      high[M++] = INF + 1;
    }
  }

  int find(int i) {
    if (root[i] != i) {
      root[i] = find(root[i]);
    }
    return root[i];
  }

  void merge(int i, int j, int e) {
    i = find(i);
    j = find(j);
    if (i == j) {
      return;
    }
    if (rank[i] > rank[j]) {
      swap(i, j);
    }
    root[i] = j;
    if (rank[i] == rank[j]) {
      rank[j]++;
    }
    // Make both components' tree M children of a new node.
    children[M][0] = node[i];
    children[M][1] = node[j];
    high[M] = e;
    node[j] = M++;
  }
};

struct HeavyLightTree {
  int heavy[LIM2];
  int root[LIM2], treePos[LIM2], inv[LIM2];
  int ind, L[LIM2], R[LIM2];
  multiset<int> S, S2;

  int dfs(int v) {
    L[v] = ind++;
    for (int i = 0; i < LIM3 - 1; i++) {
      int p = parent[v][i];
      if (p < 0) {
        break;
      }
      parent[v][i + 1] = parent[p][i];
    }
    int size = 1, maxSubtree = 0;
    for (int u : children[v]) {
      if (u < 0) {
        continue;
      }
      parent[u][0] = v;
      int subtree = dfs(u);
      if (subtree > maxSubtree) {
        heavy[v] = u;
        maxSubtree = subtree;
      }
      size += subtree;
    }
    R[v] = ind - 1;
    return size;
  }

  void init() {
    fill_n(heavy, M, -1);
    ind = 0;
    dfs(M - 1);
    for (int i = 0, currentPos = 0; i < M; i++) {
      if (parent[i][0] == -1 || heavy[parent[i][0]] != i) {
        for (int j = i; j != -1; j = heavy[j]) {
          root[j] = i;
          inv[currentPos] = j;
          treePos[j] = currentPos++;
        }
      }
    }
    S.clear();
    S2.clear();
    S.insert(-1);
  }

  void update(int i, bool ins) {
    if (ins) {
      S.insert(treePos[i]);
      S2.insert(L[i]);
    } else {
      S.erase(S.find(treePos[i]));
      S2.erase(S2.find(L[i]));
    }
  }

  int find_closest_ancestor_set(int i) {
    while (i >= 0) {
      int j = root[i];
      int k = *prev(S.lower_bound(treePos[i] + 1));
      if (k >= treePos[j]) {
        return inv[k];
      }
      i = parent[j][0];
    }
    return -1;
  }

  bool subtree_has_set_M(int i, bool inc) {
    auto it = S2.lower_bound(L[i] + (inc ? 0 : 1));
    return it != S2.end() && *it <= R[i];
  }
};

HeavyLightTree HLT;

void update_cell(int i, bool ins) {
  // Sample is irrelevant (impossible to collect)?
  int s = S[i];
  if (s >= H[i]) {
    return;
  }
  // Register collection.
  int d = ins ? 1 : -1;
  curr.first += d;
  // Find corresponding tree node (highest valid ancestor of leaf node).
  for (int j = LIM3 - 1; j >= 0; j--) {
    if (parent[i][j] >= 0 && high[parent[i][j]] > s) {
      i = parent[i][j];
    }
  }
  // Update HLD (if deleting).
  if (!ins) {
    HLT.update(i, ins);
  }
  // Update can only be relevant if no samples in i's subtree.
  if (!HLT.subtree_has_set_M(i, true)) {
    // Find closest ancestor with sample (if any).
    int a = HLT.find_closest_ancestor_set(i);
    // Update is relevant if a doesn't exist, or if there are other samples
    // amongst a's descendants
    if (a < 0 || HLT.subtree_has_set_M(a, false)) {
      curr.second += d;
    }
  }
  // Update HLD (if inserting).
  if (ins) {
    HLT.update(i, ins);
  }
}

pair<long long, long long> solve() {
  A.clear();
  // Input.
  cin >> R >> C;
  N = R * C;
  for (int i = 0, j; i < N; i++) {
    cin >> H[i];
    if ((j = i - C) >= 0) {  // Up.
      A.emplace_back(-min(H[i], H[j]), i, j);
    }
    if (i % C > 0 && (j = i - 1) >= 0) {  // Left.
      A.emplace_back(-min(H[i], H[j]), i, j);
    }
  }
  for (int i = 0; i < N; i++) {
    cin >> S[i];
  }
  // Process edges in non-increasing order of elevation, and construct tree of
  // connected regions.
  M = 0;
  UnionFind U(N);
  sort(A.begin(), A.end());
  for (auto t : A) {
    U.merge(get<1>(t), get<2>(t), -get<0>(t));
  }
  memset(parent, -1, sizeof(parent[0]) * M);
  HLT.init();
  // Insert initial samples.
  curr = make_pair(0, 0);
  for (int i = 0; i < N; i++) {
    update_cell(i, 1);
  }
  // Process updates.
  cin >> K;
  pair<long long, long long> ans{0, 0};
  int prevY = 0;
  while (K--) {
    int i, j;
    cin >> i >> j;
    i = (i ^ prevY) - 1;
    j = (j ^ prevY) - 1;
    i = i * C + j;
    update_cell(i, 0);
    cin >> S[i];
    S[i] ^= prevY;
    update_cell(i, 1);
    ans.first += curr.first;
    ans.second += curr.second;
    prevY = curr.second;
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    auto ans = solve();
    cout << "Case #" << t << ": " << ans.first << " " << ans.second << endl;
  }
  return 0;
}