2022/round3/first_time_ch2.cpp

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