Problem: rep-ore-ting (2021 round3)

Facebulk Inc. is a mining company whose Bulk Geological Processing (BGP) network has been disrupted lately. To improve response times in the event of future disruptions, the company plans to assign shift partners within each of its \(T\) ore-processing plants.

A given plant has \(N\) employees, numbered from \(1\) to \(N\) in decreasing order of seniority.

Initially, none of the employees are partners with one another. The company will then assign \(M\) partnerships, one by one, with the \(i\)th partnership pairing up employees \(A_i\) and \(B_i\) if they weren't already. An employee can be part of multiple partnerships.

An employee \(x\) can *directly* receive reports from an employee \(y\) if \(x\) has higher seniority than \(y\) (that is, \(x < y\)), or if \(x\) and \(y\) are partners, or both. An employee \(x\) can *indirectly* receive reports from an employee \(y\) if there exists at least one intermediate employee \(z\) such that \(x\) can directly receive reports from \(z\), and \(z\) can directly or indirectly receive reports from \(y\).

Let \(S_i\) be the number of ordered pairs of employees \((x, y)\) such that employee \(x\) can directly or indirectly receive reports from employee \(y\) after the first \(i\) partnership pairings have been made. Note that \(S_i \le N(N-1)\).

Please help Facebulk evaluate its reporting efficiency over time by computing the product of \(S_{1..M}\). As this product may be very large, you should compute its value modulo \(1{,}000{,}000{,}007\).


# Constraints

\(1 \le T \le 65\)
\(2 \le N \le 2{,}000{,}000\)
\(1 \le M \le 2{,}000{,}000\)
\(1 \le A_i, B_i \le N\)
\(A_i \ne B_i\)

The sum of \(N + M\) across all plants is at most \(10{,}000{,}000\).


# Input

Input begins with an integer \(T\), the number of ore-processing plants. For each plant, there is first a line containing \(2\) space-separated integers, \(N\) and \(M\). Then, \(M\) lines follow, the \(i\)th of which contains 2 space-separated integers, \(A_i\) and \(B_i\).


# Output

For the \(i\)th plant, print a line containing *"Case #i: "* followed by a single integer, the product of \(S_{1..M}\) as defined above, modulo \(1{,}000{,}000{,}007\).


# Sample Explanation

In the first plant, after a partnership between employees \(1\) and \(2\) forms, each employee can receive reports from the other. Therefore, \(S = [2]\), and the answer is \(2 \mathrm{\;mod\;} 1{,}000{,}000{,}007 = 2\).

In the second plant, after a partnership between employees \(3\) and \(2\) forms, employee \(1\) can receive reports from employees \(2\) and \(3\), employee \(2\) can receive reports from employee \(3\), and employee \(3\) can receive reports from employee \(2\). Therefore, \(S = [4]\).

In the third plant, \(S = [7, 12]\). Each employee can receive reports from each other employee after both partnerships have been formed — for example, employee \(2\) can indirectly receive reports from employee \(1\) through employee \(4\). Therefore, the answer is \((7 \cdot 12) \mathrm{\;mod\;} 1{,}000{,}000{,}007 = 84\).

In the fourth plant, \(S = [18, 21, 25, 25]\).

In the fifth plant, \(S = [211, 217, 217, 232, 283]\).


Sample input:
5
2 1
1 2
3 1
3 2
4 2
3 2
1 4
6 4
5 3
3 6
2 4
3 6
20 5
14 8
17 20
11 14
7 2
11 17


Sample output:
Case #1: 2
Case #2: 4
Case #3: 84
Case #4: 236250
Case #5: 343501460


Solution: Each employee \(x\) can always receive reports from all lower-seniority employees \(y\) (such that \(x < y\)). This gives us \(N(N - 1) / 2\) ordered pairs of employees which are always present. What remains is counting the number of extra employee pairs \((x, y)\) such that employee \(x\) can receive reports from higher-seniority employee \(y\) (with \(x > y\)).

At each point in time, it's possible to partition all \(N\) employees into \(1\) or more groups of contiguous employees such that:
  - For each group of employees \(a..b\), each pair of employees within it can receive reports from one another (resulting in \((b-a+1)(b-a)/2\) extra employee pairs)
  - There are no extra employee pairs \((x, y)\) such that \(x\) and \(y\) are in different groups

Initially, each employee is in their own group (and there are \(0\) extra employee pairs). After the \(i\)th partnership, the groups with employees \(A_i\) and \(B_i\) (along with any other groups between them) should all get merged together (resulting in no changes if \(A_i\) and \(B_i\) are already in the same group). This is because, assuming \(A_i < B_i\), all employees throughout those groups can send reports to employee \(A_i\), who can now send reports to \(B_i\), who can in turn send reports to all other employees throughout those groups. Note that employees outside of those groups are unaffected.

This suggests a solution involving maintaining the current set of employee groups and the corresponding total number of extra employee pairs. Assuming merging of groups is implemented as a deletion of existing groups and insertion of a new group, the only operations which need to be supported are insertion/deletion of a group and searching for which group contains a given employee. If the groups are represented as an ordered set of pairs of lower/upper employees, each of these operations may be performed in \(O(\log(N))\) time, with each group insertion/deletion directly coupled with an increase/decrease to the total number of extra employee pairs.

Each employee and partnership will result in at most one group insertion, each group will be deleted at most once, and each partnership and group deletion will require at most two group searches. Therefore, the time complexity comes out to \(O((N + M) \log(N))\). It's also possible to improve this to \(O((N+M) α(N))\) by swapping out the ordered set for a [disjoint-set data structure](https://en.wikipedia.org/wiki/Disjoint-set_data_structure).

[See David Harmeyer (SecondThread)'s solution video here.](https://youtu.be/pkPaceC3Cac)


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

const int MOD = 1000000007;

long long get_seg_pairs(int a, int b) {
  long long c = b - a + 1;
  return c * (c - 1) / 2;
}

int solve() {
  // Input.
  int N, M;
  cin >> N >> M;
  long long curr = (long long)N * (N - 1) / 2;
  set<pair<int, int>> S;
  for (int i = 1; i <= N; i++) {
    curr += get_seg_pairs(i, i);
    S.emplace(i, i);
  }
  int ans = 1;
  // Process partnerships.
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    if (a > b) {
      swap(a, b);
    }
    // Find segments containing a and b.
    auto it = prev(S.lower_bound({a + 1, 0}));
    a = it->first;
    b = prev(S.lower_bound({b + 1, 0}))->second;
    // Erase all segments between those, inclusive.
    while (it != S.end() && it->second <= b) {
      curr -= get_seg_pairs(it->first, it->second);
      it = S.erase(it);
    }
    // Insert new merged segment.
    curr += get_seg_pairs(a, b);
    S.emplace(a, b);
    // Update answer.
    ans = ans * (curr % MOD) % MOD;
  }
  return ans;
}

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