Problem: valet_parking_ch2 (2021 round2)

**Note: This problem shares similarities with [Chapter 1](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-2/problems/C1/). The solution to either chapter may help with solving the other, so please consider reading both first.**

When not out fighting crime, Shaun works valet at the Fairmont hotel. Recently, he has been using his new weapon – the ten rings – to secretly help him park cars among \(T\) valet-designated garages.

The layout of a garage is a grid \(G\) of \(R\) rows (numbered from \(1\) to \(R\) from top to bottom) and \(C\) columns (numbered from \(1\) to \(C\) from left to right) of parking spaces. Initially, each space in row \(i\) and column \(j\) contains a car if \(G_{i,j} =\) "X", or is otherwise empty (if \(G_{i,j} =\) ".").

Shaun's friend, Master sorcerer Wong, has been interfering on his shift today. Wong will cast a sequence of \(S\) spells, numbered from \(1\) to \(S\). The \(i\)th spell will change whether the space at row \(A_i\) and column \(B_i\) contains a car. If that space is empty, Wong will open a portal and teleport a car into the space, whereas if the space already contains a car, Wong will teleport the car away, leaving an empty space.

After each spell, Shaun would like to consider the task of clearing out a path for easy garage access, requiring cars to be rearranged such that a certain row \(K\) contains no cars in any of its \(C\) spaces. To that end, the magic of the ten rings supports the following \(3\) types of moves:

1. Levitate any car out of the garage and onto the street, leaving its space empty (and the position of all other cars unchanged).
2. Shift all the cars in the garage upwards. For each car in the garage, it moves from its current parking space to the space just above it, unless there's either no such space (due to the car being in row \(1\)) or that space is occupied by a car which is remaining stationary, in which case this car itself remains stationary.
3. Shift all the cars in the garage downwards (similarly to #2).

For example, a sequence of two moves of type #2 is illustrated below:

```
  X..   XXX   XXX
  .XX   ..X   XXX
  ..X   XXX   ..X
  XXX   ...   ...
```

Note that while Shaun must strategize a sequence of moves after each spell, he never carries them out (leaving only Wong's spells to make actual changes to the garage).

Let \(M_i\) be the minimum number of moves which would theoretically be required to leave row \(K\) empty starting from the state of the garage after the first \(i\) spells have been cast. Please help Shaun compute the sum \(M_1 + M_2 + ... + M_S\).


# Constraints

\(1 \le T \le 50\)
\(1 \le R, C \le 2{,}000{,}000\)
\(R*C \le 2{,}000{,}000\)
\(1 \le K \le R\)
\(1 \le S \le 2{,}000{,}000\)
\(G_{i,j} \in \{\)".", "X"\(\}\)
\(1 \le A_i \le R\)
\(1 \le B_i \le C\)

The sum of \(R*C + S\) across all garages is at most \(13{,}000{,}000\).


# Input

Input begins with an integer \(T\), the number of garages in which Shaun must consider clearing a path. For each garage, there is first a line containing \(4\) space-separated integers \(R\), \(C\), \(K\), and \(S\). Then, \(R\) lines follow, the \(i\)th of which contains the \(C\) characters \(G_{i,1..C}\). Finally, \(S\) lines follow, the \(i\)th of which contains \(2\) space-separated integers \(A_i\) and \(B_i\).


# Output

For the \(i\)th garage, print a line containing *"Case #i: "* followed by a single integer, the sum \(M_1 + M_2 + ... + M_S\).


# Sample Explanation

In the first garage, there is a single occupied space. Wong's first spell removes the car, after which the row is already cleared (i.e. \(M_1 = 0\)). After Wong's second spell refills the space, it would take a move of type #1 to clear the row (\(M_2 = 1\)). The answer is thus \(0 + 1 = 1\).

The second garage looks as follows after Wong's single spell, in which row \(2\) is already cleared and no moves are required:

```
  XXX
  ...
  XXX
```

The third garage looks as follows after Wong's single spell:

```
  XXX
  .X.
  XXX
```

One optimal strategy is for Shaun to use a move of type #1 to remove the car in row \(1\) and column \(2\), followed by a move of type #3 to shift all cars downwards, resulting in the following valid arrangement:

```
  ...
  XXX
  XXX
```
  
For the fourth garage, \(M = [1, 2, 2, 1, 0]\), and so the answer is \(1 + 2 + 2 + 1 + 0 = 6\).

For the sixth garage, \(M = [5, 4, 4, 4, 3]\).


Sample input:
6
1 1 1 2
X
1 1
1 1
3 3 2 1
XXX
.X.
XXX
2 2
3 3 1 1
XXX
...
XXX
2 2
4 3 4 5
...
.XX
..X
XXX
1 1
1 3
4 1
4 2
4 3
4 5 3 1
.X.X.
.XXX.
X.X.X
X.X.X
2 3
7 8 4 5
..XX.X.X
X..X.X..
XX....XX
.XXX.XX.
X...XX.X
..X.....
.X..X.X.
1 1
4 4
7 7
3 7
3 1


Sample output:
Case #1: 1
Case #2: 0
Case #3: 2
Case #4: 6
Case #5: 2
Case #6: 20


Solution: As in Chapter 1, for each state of the garage, we can think of an optimal solution as consisting of performing \(|i-K|\) shift moves to arrive at some target row \(i\) (such that \(0 \le i \le R+1\)), followed by the removal of every car ultimately present in row \(K\).

Let \(V_i\) be the total number of moves required to use target row \(i\). Initially, assuming no cars, \(V_i = |i-K|\). We'll then need to maintain the values \(V_{0..(R+1)}\) based on cars getting added or removed (including adding each car initially present in the garage), and be able to query the minimum of these values to compute each required \(M\) value. To help with this, we'll maintain a [segment tree](https://en.wikipedia.org/wiki/Segment_tree) over the \(V\) values, with each segment tree node storing the minimum of the values in its interval.

Along the way, for each column \(j\), we'll need to be able to efficiently determine the row \(A_j\) of its \((R-K+1)\)th car from the top (if any), and the row \(B_j\) of its \(K\)th car from the bottom (if any). These are important because the column contributes \(1\) car for each target row \(i\) such that \(i < A_j\), \(i > B_j\), and/or \(G_{i,j} =\) "X". One approach is to maintain an ordered set of car positions in each column, pre-populated with \(R-K+1\) dummy cars above row \(1\) and \(K\) below row \(R\), and with pointers to the two relevant cars maintained. Another approach involves order statistics using a Fenwick (binary indexed) tree. Either way, we'll be able to add/remove cars and determine \(A_j\) and \(B_j\) in at most \(O(\log(R))\) time each.

What remains is updating all of the above whenever a car gets added or removed. Each time this occurs, a single \(G\) value changes, and a single column's \(A\) and \(B\) values may change. This can be translated into at most \(3\) increments or decrements of ranges of \(V\) values, which can each be handled in \(O(\log(R))\) time using lazy propagation. The overall time complexity of this solution is therefore \(O((R\cdot C + S) \log(R))\).

As in Chapter 1, it can also be observed that only target rows within \(C\) rows of row \(K\) need to be considered, as shifting to further target rows must take longer than sticking with a target row of \(K\) and removing all its cars. This opens the door to an \(O(S\cdot\min(R, C) + (R\cdot C + S) \log(R))\) variation on the above solution, in which the segment tree is removed in favour of simply iterating over all individual \(V\) values within the relevant interval of rows to update and query them.

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


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

const int LIM = 2000005;

template<class T>
class segment_tree {
  static T join_values(const T &a, const T &b) {
    return min(a, b);
  }

  static T join_value_with_delta(const T &v, const T &d, int len) {
    return v + d;
  }

  static T join_deltas(const T &d1, const T &d2) {
    return d1 + d2;
  }

  int len;
  vector<T> value, delta;
  vector<bool> pending;

  void build(int i, int lo, int hi, const T &v) {
    if (lo == hi) {
      value[i] = v;
      return;
    }
    int mid = lo + (hi - lo)/2;
    build(i*2 + 1, lo, mid, v);
    build(i*2 + 2, mid + 1, hi, v);
    value[i] = join_values(value[i*2 + 1], value[i*2 + 2]);
  }

  void push_delta(int i, int lo, int hi) {
    if (pending[i]) {
      value[i] = join_value_with_delta(value[i], delta[i], hi - lo + 1);
      if (lo != hi) {
        int l = 2*i + 1, r = 2*i + 2;
        delta[l] = pending[l] ? join_deltas(delta[l], delta[i]) : delta[i];
        delta[r] = pending[r] ? join_deltas(delta[r], delta[i]) : delta[i];
        pending[l] = pending[r] = true;
      }
      pending[i] = false;
    }
  }

  T query(int i, int lo, int hi, int tgt_lo, int tgt_hi) {
    push_delta(i, lo, hi);
    if (lo == tgt_lo && hi == tgt_hi) {
      return value[i];
    }
    int mid = lo + (hi - lo)/2;
    if (tgt_lo <= mid && mid < tgt_hi) {
      return join_values(
                query(i*2 + 1, lo, mid, tgt_lo, min(tgt_hi, mid)),
                query(i*2 + 2, mid + 1, hi, max(tgt_lo, mid + 1), tgt_hi));
    }
    if (tgt_lo <= mid) {
      return query(i*2 + 1, lo, mid, tgt_lo, min(tgt_hi, mid));
    }
    return query(i*2 + 2, mid + 1, hi, max(tgt_lo, mid + 1), tgt_hi);
  }

  void update(int i, int lo, int hi, int tgt_lo, int tgt_hi, const T &d) {
    push_delta(i, lo, hi);
    if (hi < tgt_lo || lo > tgt_hi) {
      return;
    }
    if (tgt_lo <= lo && hi <= tgt_hi) {
      delta[i] = d;
      pending[i] = true;
      push_delta(i, lo, hi);
      return;
    }
    update(2*i + 1, lo, (lo + hi)/2, tgt_lo, tgt_hi, d);
    update(2*i + 2, (lo + hi)/2 + 1, hi, tgt_lo, tgt_hi, d);
    value[i] = join_values(value[2*i + 1], value[2*i + 2]);
  }

 public:
  segment_tree(int n, const T &v = T())
      : len(n), value(4*len), delta(4*len), pending(4*len, false) {
    build(0, 0, len - 1, v);
  }

  int size() const { return len; }
  T at(int i) { return query(i, i); }
  T query(int lo, int hi) { return query(0, 0, len - 1, lo, hi); }
  void update(int i, const T &d) { update(0, 0, len - 1, i, i, d); }
  void update(int lo, int hi, const T &d) { update(0, 0, len - 1, lo, hi, d); }
};

int R, C, K, S;
string G[LIM];
set<int> B[LIM];
set<int>::iterator I1[LIM], I2[LIM];

void add_car(segment_tree<int> &st, int r, int c) {
  // Shrink valid range.
  int i1 = *I1[c], i2 = *I2[c];
  B[c].insert(r);
  if (r > i1) {
    I1[c]++;
    st.update(i1 + 1, *I1[c] - 1, 1);
  }
  if (r < i2) {
    I2[c]--;
    st.update(*I2[c] + 1, i2 - 1, 1);
  }
  // Update added car index if in valid range.
  if (*I1[c] <= r && r <= *I2[c]) {
    st.update(r, r, 1);
  }
}

void remove_car(segment_tree<int> &st, int r, int c) {
  // Grow valid range.
  int i1 = *I1[c], i2 = *I2[c];
  if (r >= i1) {
    I1[c]--;
    st.update(*I1[c] + 1, i1 - 1, -1);
  }
  if (r <= i2) {
    I2[c]++;
    st.update(i2 + 1, *I2[c] - 1, -1);
  }
  B[c].erase(r);
  // Update removed car index if in valid range.
  if (*I1[c] <= r && r <= *I2[c]) {
    st.update(r, r, -1);
  }
}

long long solve() {
  for (int i = 0; i < LIM; i++) {
    B[i].clear();
    G[i].clear();
  }
  cin >> R >> C >> K >> S;
  for (int j = 0; j < C; j++) {
    // R - K + 1 cars before the beginning.
    for (int i = R - K; i >= 0; i--) {
      B[j].insert(-1 - i);
    }
    I1[j] = B[j].begin();
    // K cars after the end.
    for (int i = K - 1; i >= 0; i--) {
      B[j].insert(R + 2 + i);
    }
    I2[j] = prev(B[j].end());
  }
  segment_tree<int> st(R + 2);
  for (int i = 0; i <= R + 1; i++) {
    st.update(i, i, abs(i - K));
    if (1 <= i && i <= R) {
      cin >> G[i];
      for (int j = 0; j < C; j++) {
        if (G[i][j] == 'X') {
          add_car(st, i, j);
        }
      }
    }
  }
  long long ans = 0;
  while (S--) {
    int i, j;
    cin >> i >> j;
    j--;
    if (G[i][j] == 'X') {
      G[i][j] = '.';
      remove_car(st, i, j);
    } else {
      G[i][j] = 'X';
      add_car(st, i, j);
    }
    ans += st.query(0, R + 1);
  }
  return ans;
}

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