1017. How Many Pairs Are Joined Now
A company has n exchanges. Exchange i serves w[i] customers, and all the
customers of one exchange can already reach one another. Then q cables arrive, each joining
the group holding exchange u and the group holding exchange v.
After EVERY cable, print how many unordered pairs of DISTINCT customers can reach each other.
``` 3 exchanges serving 2, 3, 1 customers
before anything: 1 + 3 + 0 = 4 pairs cable 1-2 -> 10 the group serves 5, and 5 * 4 / 2 = 10 cable 2-3 -> 15 the group serves 6, and 6 * 5 / 2 = 15 ```
4 exchanges serving 1 each, cables (1 2)(3 4)(1 3) -> 1 2 6
2 exchanges serving 50000 each, cable (1 2) -> 4999950000
Customers at the same exchange count as a pair, which is why the first line of the first example is 4 before any cable is laid at all.
## What most people try first
Recompute the whole total after each cable: walk the exchanges, add up the customers of each
group, and sum s(s-1)/2 over the groups. That is O(n) per cable and O(n q) in total,
about 5 * 10^8 at the limits with a large constant, and it throws away work every time.
## Only the new cross pairs are new
Keep, on each root, the TOTAL number of customers in that group. When two groups of a and
b customers are joined, the pairs that were not reachable before and are now are exactly
the pairs with one customer on each side, and there are a * b of them. So:
total = sum over i of w[i] * (w[i] - 1) / 2
for each cable (u, v):
ru = find(u); rv = find(v)
if ru != rv:
total = total + served[ru] * served[rv]
merge, and set served of the new root to the sum
print total
## Why a * b is exactly the increase
Before the cable, the reachable pairs inside the two groups are a(a-1)/2 and b(b-1)/2.
Afterwards the joined group contributes (a+b)(a+b-1)/2. Subtract:
(a+b)(a+b-1)/2 - a(a-1)/2 - b(b-1)/2 = a*b
and every other group is untouched. No division is needed in the loop at all, which is worth having: the running total is built from products and never from a halved quantity that might be odd at the wrong moment.
## Overflow, and this one is real
The customers add up to at most 6 * 10^4 * 5 * 10^4 = 3 * 10^9, so the final total reaches
about 4.5 * 10^18. That fits in a signed 64 bit integer, whose maximum is
9223372036854775807, and nowhere near a signed 32 bit one, whose maximum is 2147483647.
Two exchanges of 50000 customers each already give 4999950000 after one cable, which is the
third example and is in the tests. A 32 bit accumulator wraps it to 704982704.
The product served[ru] * served[rv] must ALSO be computed in 64 bits. Two groups of
1.5 * 10^9 customers multiply to 2.25 * 10^18, so casting only the result and not the
operands is the version that still fails.
## The merge that adds nothing
A cable whose two exchanges are already in one group adds no pair at all, and adding
served[r] * served[r] there would be a large wrong number rather than a small one. The root
comparison is what prevents it.
## Cross-reference
Problem 398 counts the same pairs on a FIXED graph, once, with a traversal, and sums
s(s-1)/2 over the components at the end. This one is asked after every cable and is
weighted, which is what turns the sum into an increment.
## Cost
Time O(n + q alpha(n)). Space O(n).
Constraints - `1 ≤ n ≤ 60000` - `1 ≤ q ≤ 200000` - `1 ≤ w[i] ≤ 50000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, and a pair may repeat.
Input
The first line contains two integers n and q.
The second line contains n integers w[1] ... w[n], the customers served by each exchange.
Each of the next q lines contains two integers u and v.
Output
Print q lines. Line i holds one integer, the number of unordered pairs of distinct customers that can reach each other after the ith cable. Print the numbers alone, one per line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.