hackercupai/hackercup huggingface dataset:
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)