Problem: first_time_ch2 (2022 round3)

**Note: The only difference between this and [Chapter 1](https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-3/problems/D1/) is that here, you must find the sum of answers for \(K = 1..N\).**

Boss Rob ain’t Som Tawyer, but he can paint a fence alright.

Rob's fence is made of \(N\) wooden stakes, numbered \(1\) to \(N\) from left to right. Initially (at time \(0\)), the \(i\)th stake is of color \(i\). There is a fencepost before stake \(1\) and after stake \(N\), as well as after every \(K\)th stake starting from the left.

Rob has a simple and joyful plan to repaint his fence, consisting of \(M\) moments in time. At time \(i\), he'll repaint all stakes which are color \(A_i\) to color \(B_i\). Doing so, when would be the *first time* that all pairs of stakes not separated by a fencepost have the same color? If it will never occur, consider the answer to be \(-1\).

Rob is still on the _fence_ about the value of \(K\), so please print **the sum of answers over \(K = 1..N\).** Sorry for the pun (we know there is a lot at _stake_ in this round _gating_ the finals). In our de​_fence_, it makes for good _post_-problem content.

# Constraints

\(1 \le T \le 30\)
\(1 \le N, M \le 600{,}000\)
\(1 \le A_i, B_i \le N\)
\(A_i \ne B_i\)

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


# Input Format

Input begins with an integer \(T\), the number of test cases. For the \(i\)th test case, there is first a line containing two space-separated integers \(N\) and \(M\). Then, \(M\) lines follow, the \(i\)th of which contains two space-separated integers \(A_i\) and \(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 answers for each \(K = 1..N\).


# Sample Explanation

The progressions of fences for the first two sample cases are depicted below (with fenceposts depicted for \(K=2\) and \(K=3\) respectively):

{{PHOTO_ID:631752615085471|WIDTH:700}}

In the first case, the answers are \([0, 2, 4, 3, 4]\) for \(K = 1..5\), so we print \(2+4+3+4 = 13\).

In the second case, the answers are \([0, 1, 3]\) for \(K = 1..3\), so we print \(1+3=4\).

In the third case, the fence (with fenceposts depicted for \(K=3\)) progresses as follows:

{{PHOTO_ID:413921204256250|WIDTH:700}}

For \(K = 1..8\), the answers are \([0, 5, -1, 6, -1, -1, -1, -1]\), so we print the sum \(6\).



Sample input:
3
5 4
2 1
3 4
1 4
5 4
3 4
1 2
2 1
1 3
3 1
8 6
1 4
2 3
4 3
8 7
6 5
7 5


Sample output:
Case #1: 13
Case #2: 4
Case #3: 6


Solution: We can still use the overall \(O(M + N \log N)\) disjoint sets strategy as in the previous chapter, but we can no longer keep track of colors in fixed bins. Let's switch to a different approach.

At any time, consider grouping consecutive balls of the same color (i.e. DSU representative) into \(G\) maximal groups. We can express this as a partition of \(N\), namely, a sequence of line segments \(S_1, ..., S_G\) with lengths summing to \(N\), where the color of stakes in each segment is uniform.

*Case 1*: Assume that \(N\) evenly divides \(K\). We can see that this partition is uniformly colored over every \(K\) stakes if \(K\) is a divisor of the lengths of all \(G\) segments. This is equivalent to requiring \(K\) be a divisor of \(\text{gcd}(S_1, ..., S_G)\). As long as we have the GCD, we can enumerate through all its divisors \(k\) and conclude that all bins of size \(k\) are uniformly colored.

*Case 2*: What if \(N\) doesn't divide \(K\)? We'll be left with a rightmost "remainder" bin of some length less than \(K\). Denote its length by \(R\):
* If the last segment's length \(|S_G| < K\), then the answer is NO, because the last two segments, having different colors, will necessarily overlap the last bin.
* Else \(|S_G| \ge K\), and we can consider breaking up \(S_G\) into two segments of lengths \(L = |S_G| - R\) and \(R\) (the right most bin) where \(|S_1| + ... + |S_{G-1}| + L\) evenly divides \(K\). Since stakes \(R..N\) are already the same color, this reduces to checking if \(K\) is a divisor of \(\text{gcd}(S_1, ..., S_{G-1}, L)\), which also requires \(K\) to be a divisor of \(\text{gcd}(S_1, ..., S_{G-1})\).

Case 2 simply reduces to running case 1 on all but the last segment.

We can use a data structure like an [implicit treap](https://cp-algorithms.com/data_structures/treap.html) to maintain the merging and splitting of segments in \(\mathcal{O}(\log N\)) time per insert/delete/access/select_kth operation. Whenever we update \(\text{parent}[i] = j\) in the DSU, we consider whether this breaks up an existing segment (of length longer than \(1\)) that \(i\) is part of, or whether it makes the parent of stake \(i\) equal to the preceding or following segment, in which case it can be merged.

The implicit treap also supports dynamic range queries like a segment tree, which we can use for the GCD. After each update, we query the GCD of the segment lengths and loop through up to \(\mathcal{O}(\sqrt{N})\) divisors. The overall running time is \(\mathcal{O}(M \sqrt N + N \log N)\).


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

struct segment {
  int l, r, rep, gcd;

  segment(int _l = 0, int _r = 0, int _rep = -1, int _gcd = 0)
      : l(_l), r(_r), rep(_rep), gcd(_gcd ? _gcd : (r - l + 1)) {}

  int length() const { return r - l + 1; }
};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
class implicit_treap {
  static T join_values(const T &a, const T &b) {
    // Really, only the GCD matters for non-leaf nodes.
    return segment(min(a.l, b.l), max(a.r, b.r), 0,
                   __gcd((unsigned)a.gcd, (unsigned)b.gcd));
  }

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

  struct node_t {
    T value, subtree_value, delta;
    bool pending;
    int size, priority;
    node_t *left, *right;

    node_t(const T &v)
        : value(v),
          subtree_value(v),
          pending(false),
          size(1),
          priority(rng()),
          left(nullptr),
          right(nullptr) {}
  } * root;

  static int size(node_t *n) { return (n == nullptr) ? 0 : n->size; }

  static void update_value(node_t *n) {
    if (n == nullptr) {
      return;
    }
    n->subtree_value = n->value;
    if (n->left != nullptr) {
      n->subtree_value = join_values(n->subtree_value, n->left->subtree_value);
    }
    if (n->right != nullptr) {
      n->subtree_value = join_values(n->subtree_value, n->right->subtree_value);
    }
    n->size = 1 + size(n->left) + size(n->right);
  }

  static void update_delta(node_t *n, const T &d) {
    if (n != nullptr) {
      n->delta = n->pending ? join_deltas(n->delta, d) : d;
      n->pending = true;
    }
  }

  static void push_delta(node_t *n) {
    if (n == nullptr || !n->pending) {
      return;
    }
    n->value = join_value_with_delta(n->value, n->delta, 1);
    n->subtree_value =
        join_value_with_delta(n->subtree_value, n->delta, n->size);
    if (n->size > 1) {
      update_delta(n->left, n->delta);
      update_delta(n->right, n->delta);
    }
    n->pending = false;
  }

  static void merge(node_t *&n, node_t *left, node_t *right) {
    push_delta(left);
    push_delta(right);
    if (left == nullptr) {
      n = right;
    } else if (right == nullptr) {
      n = left;
    } else if (left->priority < right->priority) {
      merge(left->right, left->right, right);
      n = left;
    } else {
      merge(right->left, left, right->left);
      n = right;
    }
    update_value(n);
  }

  static void split(node_t *n, node_t *&left, node_t *&right, int i) {
    push_delta(n);
    if (n == nullptr) {
      left = right = nullptr;
    } else if (i <= size(n->left)) {
      split(n->left, left, n->left, i);
      right = n;
    } else {
      split(n->right, n->right, right, i - size(n->left) - 1);
      left = n;
    }
    update_value(n);
  }

  static void insert(node_t *&n, node_t *new_node, int i) {
    push_delta(n);
    if (n == nullptr) {
      n = new_node;
    } else if (new_node->priority < n->priority) {
      split(n, new_node->left, new_node->right, i);
      n = new_node;
    } else if (i <= size(n->left)) {
      insert(n->left, new_node, i);
    } else {
      insert(n->right, new_node, i - size(n->left) - 1);
    }
    update_value(n);
  }

  static void erase(node_t *&n, int i) {
    push_delta(n);
    if (i == size(n->left)) {
      delete n;
      merge(n, n->left, n->right);
    } else if (i < size(n->left)) {
      erase(n->left, i);
    } else {
      erase(n->right, i - size(n->left) - 1);
    }
    update_value(n);
  }

  static node_t *select(node_t *n, int i) {
    push_delta(n);
    if (i < size(n->left)) {
      return select(n->left, i);
    }
    if (i > size(n->left)) {
      return select(n->right, i - size(n->left) - 1);
    }
    return n;
  }

  template <typename TComp>
  static int rank(node_t *n, const TComp &cmp) {
    // assert(n != nullptr);
    push_delta(n);
    int r = size(n->left), cmp_res = cmp(n->value);
    if (cmp_res < 0) {
      return rank(n->left, cmp);
    }
    if (cmp_res > 0) {
      return rank(n->right, cmp) + r + 1;
    }
    return r;
  }

  void clean_up(node_t *&n) {
    if (n != nullptr) {
      clean_up(n->left);
      clean_up(n->right);
      delete n;
    }
  }

 public:
  implicit_treap(int n = 0, const T &v = T()) : root(nullptr) {
    for (int i = 0; i < n; i++) {
      push_back(v);
    }
  }

  template <class It>
  implicit_treap(It lo, It hi) : root(nullptr) {
    for (; lo != hi; ++lo) {
      push_back(*lo);
    }
  }

  ~implicit_treap() { clean_up(root); }
  int size() const { return size(root); }
  bool empty() const { return root == nullptr; }
  void insert(int i, const T &v) { insert(root, new node_t(v), i); }
  void erase(int i) { erase(root, i); }
  void push_back(const T &v) { insert(size(), v); }
  void pop_back() { erase(size() - 1); }
  T at(int i) const { return select(root, i)->value; }
  void update(int i, const T &d) { update(i, i, d); }

  void update(int lo, int hi, const T &d) {
    node_t *l1, *r1, *l2, *r2, *t;
    split(root, l1, r1, hi + 1);
    split(l1, l2, r2, lo);
    update_delta(r2, d);
    merge(t, l2, r2);
    merge(root, t, r1);
  }

  T query(int lo, int hi) {
    node_t *l1, *r1, *l2, *r2, *t;
    split(root, l1, r1, hi + 1);
    split(l1, l2, r2, lo);
    T res = r2->subtree_value;
    merge(t, l2, r2);
    merge(root, t, r1);
    return res;
  }

  template <typename TComp>
  int rank(const TComp &cmp) const {
    return rank(root, cmp);
  }
};

implicit_treap<segment> T;

void update_parent(int i, int p_new) {
  // Find the rank j of the segment containing i.
  int j = T.rank([&](const segment &s) {
    return i < s.l ? -1 : (i > s.r ? 1 : 0);
  });
  segment curr = T.at(j);
  if (curr.length() == 1) {
    // Just update it.
    curr.rep = p_new;
    T.update(j, curr);
  } else {
    // Break up the segment.
    segment lseg(curr.l, i - 1, curr.rep);
    segment mseg(i, i, p_new);
    segment rseg(i + 1, curr.r, curr.rep);
    // Erase the old segment.
    T.erase(j);
    // Insert new segs, if non-zero length.
    if (rseg.length() > 0) {
      T.insert(j, rseg);
    }
    T.insert(j, mseg);
    curr = mseg;
    if (lseg.length() > 0) {
      T.insert(j, lseg);
      j++;  // Make sure j still points to mseg.
    }
    // If j is broken up of 2 segments, then we might still need to merge it.
  }
  // If segment j - 1 has rep p_new, merge segment j left with j - 1.
  if (j - 1 >= 0 && T.at(j - 1).rep == p_new) {
    segment prev(T.at(j - 1).l, curr.r, p_new);
    T.update(j - 1, prev);
    T.erase(j);
    curr = prev;  // Set curr to the merged segment.
    j--;
  }
  // If segment j + 1 has rep p_new, merge segment j right with j + 1.
  if (j + 1 < T.size() && T.at(j + 1).rep == p_new) {
    segment next(curr.l, T.at(j + 1).r, p_new);
    T.update(j + 1, next);
    T.erase(j);
  }
}

struct disjoint_sets {
  vector<vector<int>> values;
  vector<int> parent, color_of_parent, parent_of_color;

 public:
  disjoint_sets(int N)
      : values(N), parent(N), color_of_parent(N), parent_of_color(N) {
    for (int i = 0; i < N; i++) {
      values[i] = {i};
      parent[i] = i;
      color_of_parent[i] = i;
      parent_of_color[i] = i;
    }
  }

  // O(M + N log N) across M calls to unite(), not including update_parent().
  void unite(int a, int b) {
    a = parent[a];
    b = parent[b];
    if (a != b) {
      if (values[a].size() < values[b].size()) {
        swap(a, b);
      }
      while (!values[b].empty()) {
        int v = values[b].back();
        values[b].pop_back();
        update_parent(v, a);
        parent[v] = a;
        color_of_parent[v] = color_of_parent[a];
        values[a].push_back(v);
      }
    }
  }

  void repaint(int c1, int c2) {
    int pa = parent_of_color[c1];
    if (pa == -1) {
      return;
    }
    color_of_parent[pa] = c2;
    parent_of_color[c1] = -1;
    int pb = parent_of_color[c2];
    if (pb == -1) {
      parent_of_color[c2] = pa;
      return;
    }
    unite(pa, pb);
    color_of_parent[pb] = c2;
    parent_of_color[c2] = parent[pb];
  }
};

long long solve() {
  int N, M;
  cin >> N >> M;
  vector<int> A(M), B(M), ans(N + 1, -1);
  disjoint_sets DS(N);
  for (int i = 0; i < M; i++) {
    cin >> A[i] >> B[i];
    --A[i], --B[i];
  }
  ans[0] = ans[1] = 0;
  // Initialize segments.
  T = implicit_treap<segment>();
  for (int i = 0; i < N; i++) {
    T.push_back(segment(i, i, i));
  }
  for (int i = 0; i < M; i++) {
    DS.repaint(A[i], B[i]);
    if (T.size() == 1) {
      // All segments are unified. All K_i's are possible now.
      for (int k = 1; k <= N; k++) {
        if (ans[k] == -1) {
          ans[k] = i + 1;
        }
      }
      break;
    }
    auto update_ans = [&](int k, int t) {
      if (ans[k] == -1) {
        ans[k] = t + 1;
      }
    };
    for (int lastseg : {T.size() - 1, T.size() - 2}) {
      int gcd = T.query(0, lastseg).gcd;
      update_ans(gcd, i);  // Directly update any K = gcd.
      double lim = sqrt(gcd);
      for (int d = 1; d <= lim; d++) {
        if (gcd % d == 0) {
          if (gcd / d != d) {
            update_ans(d, i);
          }
          update_ans(gcd / d, i);
        }
      }
    }
  }
  return accumulate(ans.begin(), ans.end(), 0LL);
}

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;
}