Problem: perfectly_balanced_ch2 (2022 round2)

**Note: This is the harder version of [Chapter 1](https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-2/problems/A1). This version involves an array of integers instead of a string, and the array may change with updates.**

An array is *perfectly balanced* if its length is even, and the first half of the array can be shuffled to make the array a palindrome. For example, \([15,2,15,2]\) and \([7,5,5,7]\) are perfectly balanced, but \([7,5,3,1,3,5,7]\) and \([3,1,1,3,2,3]\) are not.

An array is *almost perfectly balanced* if you can delete exactly one element from it to make it perfectly balanced. Some examples are \([1, 2, 3, 4, 4, 5, 1, 3, 2]\), \([1]\), and \([2, 2, 2, 3, 2]\).

{{PHOTO_ID:532712048616543|WIDTH:700}}

You are given a larger template array \(A_1 ... A_N\) of length \(N\), along with \(Q\) events, the \(i\)th of which is one of the following two formats:

- \(1\) \(X_i\) \(Y_i\): set \(A_{X_i}\) to \(Y_i\).
- \(2\) \(L_i\) \(R_i\): check whether the subarray \(A_{L_i..R_i}\) is almost perfectly balanced.

For how many type-2 queries is the subarray almost perfectly balanced?


# Constraints

\(1 \le T \le 85\)
\(1 \le N \le 10^6\)
\(1 \le A_i \le 10^6\)
\(1 \le Q \le 10^6\)
\(1 \le X_i \le N\)
\(1 \le Y_i \le 10^6\)
\(1 \le L_i \le R_i \le N\)

The sum of \(N\) across all test cases is at most \(4{,}000{,}000\).
The sum of \(Q\) across all test cases is at most \(4{,}000{,}000\).


# Input Format

Input begins with a single integer \(T\), the number of test cases. For each test case, there is first a line containing a single integer \(N\). Then, there is a line containing \(N\) space-separated integers \(A_1, ..., A_N\). Then, there is a line containing a single integer \(Q\). Then, \(Q\) lines follow, the \(i\)th of which contains three space-separated integers, either "\(1\) \(X_i\) \(Y_i\)" or "\(2\) \(L_i\) \(R_i\)".


# Output Format

For the \(i\)th test case, output a single line containing `"Case #i: "`, followed by a single integer: the number of queries which are an almost perfectly balanced subarray.


# Sample Explanation

In the first case, the template array is \([2,1,5,1,5,1]\).

For the first query, the subarray is \([1,5,1,5,1]\). You can delete the second \(1\) to get \([1,5,5,1]\), which is a palindrome. Thus, \([1,5,1,5,1]\) is an almost perfectly balanced subarray.

For the second query, the subarray is \([2,1,5,1,5]\). You can delete the \(2\) to get \([1,5,1,5]\) then reorder the first half of the array to get \([5,1,1,5]\), which is a palindrome. Thus, \([2,1,5,1,5]\) is an almost perfectly balanced subarray.

For the third query, the subarray is \([2,1,5]\). You cannot delete any element to get an almost perfectly balanced subarray.

The next two events are updates, after which the template array is \([5, 5, 5, 1, 5, 1]\).

For the fourth query, the subarray is \([5,5,5]\). You can delete any element to get \([5,5]\), which is a palindrome. Thus, \([5,5,5]\) is an almost perfectly balanced subarray.

The fifth, sixth, eighth, and tenth queries are also almost perfectly balanced subarrays, so the final answer is \(7\).


Sample input:
1
6
2 1 5 1 5 1
17
2 2 6
2 1 5
2 1 3
1 1 5
1 2 5
2 1 3
2 1 5
2 2 2
1 3 1000000
2 1 5
2 1 3
2 2 4
2 4 6
1 6 1000000
2 4 6
1 5 1000000
2 5 6


Sample output:
Case #1: 7


Solution: Having to now deal with updates on numbers up to \(10^6\), we can no longer use prefix sums as in chapter 1. Instead, let's consider a hashing approach. We'll need a hash function defined over subarrays, some \(h(A_{l..r})\) that is only sensitive to the frequency of its input values (i.e. is agnostic to the order they are in), along with a strategy to update the hashes and quickly query the hash of any subarray. Most importantly, we should be able to compare the two hashes and deduce whether their corresponding subarrays differ by exactly one number.

One strategy is to first pick your favorite hash function \(h : [1, 10^6] \to [0, P)\) on a single integer, where \(P\) is some large prime number, then define \(h(A_{l..r}) := (h(A_l) + \ldots + h(A_r)) \text{ mod } P\). It can be shown that the sum of uniformly distributed random variables mod \(P\) is itself uniformly distributed mod \(P\). Now, given two subarrays \(A_{l1..r1}\) and \(A_{l2..r2}\) with the same value frequencies except \(A_{l1..r1}\) having one extra number \(v\), we have \(h(A_{l1..r1}) - h(A_{l2..r2}) \equiv h(v) \; (\text{mod } P)\).

We can maintain a segment tree of the hashes of each \(A_i\), supporting updates and range queries for the modded sum of hashes in \(\mathcal{O}(\log N\)\) time. We can also precompute a lookup table of each \(h(A_i)\) to \(A_i\). For each query \(A_{l..r}\), again let \(m = \lfloor(l + r)/2\rfloor\). Then, we can calculate the two hash differences \(h(A_{m..r}) - h(A_{l..(m-1)})\) and \(h(A_{l..m}) - h(A_{(m+1)..r})\), checking if either one corresponds to an original value of \(A\) using the lookup table.

One concern is that if the subarrays do not differ by exactly one number, then the difference of the hashes will be garbage. It's possible for us to be unlucky and get garbage that maps back to a value in \(A\). There are ~\(10^{6}\) queries and ~\(10^{19}\) possible hash values if we hash to a \(64\)-bit range. The chances of a collision for a single hash would be \(10^{6-19} = 10^{-13}\). The chances of at least one collision across any of the \(10^6\) queries would be roughly \(1 - \left(1-10^{-13}\right)^{10^6} \approx 10^{-7}\). With a good base hash function and seed, this should already be good enough, but in theory we can be more certain by maintaining two hash functions modulo two different primes to cross-check.

[See David Harmeyer's solution video here.](https://www.youtube.com/watch?v=w65VekVkuHA)


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

using LL = long long;
const LL MOD = (1LL << 62) - 57;
const LL SEED = chrono::steady_clock::now().time_since_epoch().count();

const LL get_hash(int v) {
  unsigned long long x = v + SEED;
  // http://xorshift.di.unimi.it/splitmix64.c
  x += 0x9e3779b97f4a7c15;
  x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  return (x ^ (x >> 31)) % MOD;
}

LL add(LL a, LL b) { return (a % MOD + b % MOD) % MOD; }
LL sub(LL a, LL b) { return ((a - b) % MOD + MOD) % MOD; }

template <typename T>
class segment_tree {
  static T join_values(const T &a, const T &b) { return add(a, b); }
  static T join_value_with_delta(const T &v, const T &d) { return d; }

  int len;
  vector<T> value;

  template <typename It>
  void build(int i, int lo, int hi, It arr) {
    if (lo == hi) {
      value[i] = *(arr + lo);
      return;
    }
    int mid = lo + (hi - lo) / 2;
    build(i * 2 + 1, lo, mid, arr);
    build(i * 2 + 2, mid + 1, hi, arr);
    value[i] = join_values(value[i * 2 + 1], value[i * 2 + 2]);
  }

  T query(int i, int lo, int hi, int tgt_lo, int tgt_hi) const {
    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 target, const T &d) {
    if (target < lo || target > hi) {
      return;
    }
    if (lo == hi) {
      value[i] = join_value_with_delta(value[i], d);
      return;
    }
    int mid = lo + (hi - lo) / 2;
    update(i * 2 + 1, lo, mid, target, d);
    update(i * 2 + 2, mid + 1, hi, target, d);
    value[i] = join_values(value[i * 2 + 1], value[i * 2 + 2]);
  }

 public:
  template <typename It>
  segment_tree(It lo, It hi) : len(hi - lo), value(4 * len) {
    build(0, 0, len - 1, lo);
  }

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

int solve() {
  int N;
  cin >> N;
  vector<LL> hval(N);
  unordered_map<LL, int> hrev;
  for (int i = 0, a; i < N; i++) {
    cin >> a;
    hval[i] = get_hash(a);
    hrev[hval[i]] = a;
  }
  segment_tree<LL> ST(hval.begin(), hval.end());
  int Q;
  cin >> Q;
  int ans = 0;
  for (int i = 0, op, x, y, l, r; i < Q; i++) {
    cin >> op;
    if (op == 1) {
      cin >> x >> y;
      hval[--x] = get_hash(y);
      hrev[hval[x]] = y;
      ST.update(x, hval[x]);
    } else {
      cin >> l >> r;
      --l, --r;
      if ((r - l + 1) % 2 == 0) {
        continue;
      }
      if (l == r) {
        ans++;
        continue;
      }
      int m = (l + r) / 2;
      LL diff1 = sub(ST.query(l, m), ST.query(m + 1, r));
      LL diff2 = sub(ST.query(m, r), ST.query(l, m - 1));
      if (hrev.find(diff1) != hrev.end() || hrev.find(diff2) != hrev.end()) {
        ans++;
      }
    }
  }
  return ans;
}

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