Problem: back_in_black_ch2 (2023 round1)

*This problem shares some similarities with C1, with key differences in bold.*

A friend who works at Metal Platforms Inc just lent you a curious puzzle, offering you tickets to a metal concert if you can solve it.

The puzzle consists of \(N\) buttons in a row, numbered from \(1\) to \(N\). The initial state of button \(i\) is white if \(S_i = 1\), or black if \(S_i = 0\). Pressing a button \(k\) toggles the state of itself as well as every \(k\)th button. Your friend challenges you to return the puzzle to him with all buttons back in black.

Life is hard enough without siblings pushing your buttons. Unfortunately, your brother has taken the puzzle and will push \(Q\) buttons sequentially, the \(i\)th being button \(B_i\). 

After your brother **pushes each button**, you'd like to add to your answer the minimum number of button presses required to turn all the buttons black.

**Constraints**

\(1 \le T \le 75\)
\(1 \le N \le 4{,}000{,}000\)
\(1 \le Q \le 4{,}000{,}000\)

The sum of \(N\) and \(Q\) over all cases will be at most \(9{,}000{,}000\).

**Input Format**

Input begins with a single integer \(T\), the number of test cases. For each case, there is first a line containing a single integer \(N\). Then, there is a line containing a bitstring \(S\) of length \(N\). Then, there is a line containing a single integer \(Q\). \(Q\) lines follow, the \(i\)th of which contains a single integer \(B_i\).

**Output Format**

For the \(i\)th test case, output a single line containing `"Case #i: "` followed by a single integer, the sum of the number of button presses needed to turn all buttons black **after each of the \(Q\) presses.**

**Sample Explanation**

In the first case, after your brother presses the first button, the state of the puzzle is \(0101\). The best strategy is to press the second button, turning all lights off.

In the second case, the puzzle starts as \(0001\), and after each button press becomes \(0100\), \(0110\), \(0011\), and \(0010\) respectively. The answers after each query are \(2\), \(3\), \(2\), and \(1\) respectively, so we output their sum of \(8\).


Sample input:
5
4
1010
1
1
4
0001
4
2
3
2
4
7
0101101
8
1
3
2
6
7
4
2
5
7
0101100
1
7
7
1111111
1
1


Sample output:
Case #1: 1
Case #2: 8
Case #3: 36
Case #4: 4
Case #5: 0


Solution: In this part, it won't be efficient enough to directly simulate zeroing out the array in \(\mathcal{O}(N \log N)\) after each of the \(Q\) queries. Instead, we can track the number of presses needed as we go.

Before your brother presses anything, we can first compute the array \(P_{1..N}\) indicating whether a press is needed to zero out the initial array \(S_{1..N}\), using the same greedy algorithm from chapter 1. We can then keep a counter of the minimum number of presses needed. This part takes \(\mathcal{O}(N \log N)\) time.

From this point, if your brother presses some button \(i\) while previously \(P_i = 1\), then he has done us a favor, and we would no longer need to press that button to zero out the array. We can set \(P_i = 0\) and decrement our counter. Otherwise, if he pressed \(i\) while \(P_i = 0\) then we would now need to set \(P_i = 1\) and increment our counter.

The key is that the counter always holds the optimal number of presses to zero out the array, so we increment the overall answer by the counter after each of the \(Q\) queries. Each query takes \(\mathcal{O}(1)\) to process, so overall running time is \(\mathcal{O}(N \log N + Q)\).


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

long long solve() {
  int N, Q;
  cin >> N;
  vector<bool> white(N + 1);
  for (int i = 1; i <= N; i++) {
    char c;
    cin >> c;
    white[i] = c - '0';
  }
  vector<bool> press(N + 1);
  int num_presses = 0;
  for (int i = 1; i <= N; i++) {
    if (white[i]) {
      num_presses++;
      press[i] = 1;
      for (int j = i; j <= N; j += i) {
        white[j] = white[j] ^ 1;
      }
    }
  }
  long long ans = 0;
  cin >> Q;
  for (int i = 0, b; i < Q; i++) {
    cin >> b;
    if (press[b]) {
      num_presses--;
    } else {
      num_presses++;
    }
    press[b] = press[b] ^ 1;
    ans += num_presses;
  }
  return ans;
}

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