Problem: expl-ore-ation_ch2 (2021 round3)

**Note: Chapters [1](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-3/problems/D1) and [3](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-3/problems/D3) are strictly less and more difficult versions of this problem, respectively, 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}\).

# Constraints

\(1 \le T \le 50\)
\(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\)

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). Once \(S_{1,1}\) gets changed to \(15\), the ore sample would no longer be possible to collect. And once it gets changed back to \(5\), the sample would once again be possible to collect. Therefore, \(X = [1, 0, 1]\) and \(Y = [1, 0, 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 = Y_1 = 2\). Overall, \(X = [2, 2, 3, 3, 4]\) and \(Y = [2, 1, 1, 1, 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]\)


Sample input:
6
1 3
98 99 100
97 98 99
1
1 1 98
1 1
10
10
3
1 1 5
1 1 15
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
1 1 1
2 2 1
1 3 2
2 1 2
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
1 18 69
2 10 64
3 4 12
4 4 17
4 20 100
4 7 84
3 13 20
4 8 42
3 18 53


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: As in Chapter 1, we'll simulate the entire process in reverse, processing events for adjacent platforms becoming reachable and for rock samples needing to be collected, while maintaining a disjoint-set data structure of mutually-reachable groups of platforms. The big difference is that there are now \(RC + K\) sample collection events, each of which is only applicable to a certain interval of the \(K\) situations to be evaluated, and we'll opt to simulate all \(K\) situations simultaneously.

We can no longer store a single flag per group for whether or not a robot has already been allocated to it. However, we can expand on this concept by storing the *set of situations* (out of situations \(1..K\)) for which a robot has already allocated to the group. To make this efficient, we'll represent this as a set of contiguous intervals of situation indices.

Now, when merging two groups together, the situation interval set of the resulting group should equal the union of the two existing groups' situation interval sets. The most efficient way to implement this is to have the resulting group inherit the larger of those two existing sets, with each interval in the smaller set inserted into the larger set in turn. As part of the insertion process, any overlapping intervals should get merged together.

Finally, when processing a sample collection event for platform \((i, j)\) and for sample height \(s\) (which might either be an original \(S\) value or an updated \(U\) value) which applies to the interval of situations \(a..b\), the sample cannot be collected in any situation if \(s \ge H_{i,j}\). Otherwise, it can be collected in each of the applicable situations, meaning that we should increase the sum of \(X_{1..K}\) by \(b - a + 1\). A new robot must be allocated to collect the sample in each situation \(c\) such that \(a \le c \le b\) and platform \((i, j)\)'s group's situation interval set does not include \(c\) — for each such situation, we'll need to increment the sum of \(Y_{1..K}\), and also insert \(c\) into the group's set. This is equivalent to inserting the interval \([a, b]\) into the group's set, while increasing \(Y_{1..K}\) by \(b - a + 1\) minus the total amount of overlap between that interval and any existing ones. Any existing overlapping intervals will need to get deleted/merged as part of the interval insertion process anyway, meaning that this can all be done at once.

The most expensive part of this algorithm is handling the situation interval sets. Overall, each of the \(RC + K\) sample collection events can cause at most one situation interval to get inserted into a set, each interval can be deleted at most once, and each interval can get merged into another (larger) group's set at most \(O(\log(RC))\) times. Each insertion/deletion can be performed in \(O(\log(K))\) time, resulting in an overall \(O((RC+K) \log(RC) \log(K))\) time for these operations, with the same time complexity needed for interval queries along the way.

Alternatively, the online approach described in [Chapter 3's solution](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-3/problems/D3/solution) can also be employed here.

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


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

const int INF = 1000000000;
const int LIM = 1000002;

struct UnionFind {
  int N;
  vector<int> root, rank, sidx;
  vector<set<pair<int, int>>> S;

  UnionFind(int _N) : N(_N), root(_N), rank(_N, 0), sidx(_N), S(_N) {
    for (int i = 0; i < N; i++) {
      root[i] = i;
      sidx[i] = i;
      S[i].emplace(-INF, -INF);
      S[i].emplace(INF, INF);
    }
  }

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

  void merge(int i, int j) {
    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]++;
    }
    // Merge robot interval sets (ensuring j gets the larger one, and merging the
    // other into it).
    if (S[sidx[i]].size() > S[sidx[j]].size()) {
      swap(sidx[i], sidx[j]);
    }
    auto &SA = S[sidx[i]], &SB = S[sidx[j]];
    for (auto p : SA) {
      if (p.first == -INF || p.first == INF) {
        continue;
      }
      auto it = prev(SB.lower_bound(make_pair(p.first + 1, -1)));
      if (it->second < p.first - 1) {
        it++;
      }
      while (it->first <= p.second + 1) {
        p.first = min(p.first, it->first);
        p.second = max(p.second, it->second);
        it = SB.erase(it);
      }
      SB.insert(p);
    }
    SA.clear();
  }
};

int R, C, N, K;
int H[LIM];
vector<pair<int, int>> children[LIM];
vector<tuple<int, int, int, int>> A;

pair<long long, long long> solve() {
  A.clear();
  for (int i = 0; i < LIM; i++) {
    children[i].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]), INF, i, j);
    }
    if (i % C > 0 && (j = i - 1) >= 0) {  // Left.
      A.emplace_back(-min(H[i], H[j]), INF, i, j);
    }
  }
  for (int i = 0; i < N; i++) {
    int s;
    cin >> s;
    children[i].emplace_back(0, s);
  }
  cin >> K;
  for (int i = 0; i < K; i++) {
    int a, b, u;
    cin >> a >> b >> u;
    a--;
    b--;
    int j = a * C + b;
    if (i == 0) {
      children[j].clear();
    }
    children[j].emplace_back(i, u);
  }
  // Determine interval of situations per original/updated S value.
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < children[i].size(); j++) {
      int a = children[i][j].first;
      int b = j < int(children[i].size()) - 1
        ? children[i][j + 1].first - 1
        : K - 1;
      A.emplace_back(-children[i][j].second, i, a, b);
    }
  }
  // Process edges/samples in non-increasing order of elevation.
  UnionFind U(N);
  sort(A.begin(), A.end());
  pair<long long, long long> ans{0, 0};
  for (const auto &t : A) {
    int h = -get<0>(t), i = get<1>(t), a = get<2>(t), b = get<3>(t);
    if (i < INF) {  // Sample.
      if (H[i] <= h) {  // Impossible to collect.
        continue;
      }
      ans.first += b - a + 1;  // Collect it in each relevant situation.
      auto &S = U.S[U.sidx[U.find(i)]];
      // Add new robots to relevant situations as necessary.
      auto it = prev(S.lower_bound(make_pair(a + 1, -1)));
      if (it->second < a - 1) {
        it++;
      }
      while (it->first <= b + 1) {
        a = min(a, it->first);
        b = max(b, it->second);
        ans.second -= it->second - it->first + 1;
        it = S.erase(it);
      }
      S.emplace(a, b);
      ans.second += b - a + 1;
      continue;
    }
    U.merge(a, b);  // Edge.
  }
  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;
}