Oh, please have mercy on me

Take it easy on my heart

Even though you don't mean to hurt me

You keep tearing me apart

Would you please have mercy on me?

I'm a puppet on your string

And even though you got good intentions

I need you to set me free

I'm begging you for mercy, mercy

I'm begging you, begging you, please, baby

I'm begging you for mercy, mercy

Ooh, I'm begging you, I'm begging you, yeah

First reverse the process, adding rather than removing edges. Use meet in the middle: consider computing, for each vertex, the shortest path with $$$\left\lfloor \frac{K}{2} \right\rfloor$$$ or $$$\left\lceil \frac{K}{2} \right\rceil$$$ edges from vertex $$$1$$$ and to vertex $$$n$$$, respectively, so that each answer can be found in $$$O(n)$$$ time afterwards by enumerating the middle vertex. These two tasks are similar, so let's just consider the first one (finding shortest paths from vertex $$$1$$$). Note that we now only have to worry about paths of length up to $$$4$$$. There are several possible approaches from here. Here's the one I used:

We keep track of $$$f(i, j)$$$, the length of the shortest path from vertex 1 to vertex $$$i$$$ of length $$$j$$$ ($$$j \le 4$$$), and $$$g(i, j)$$$, the length of the shortest path from vertex $$$i$$$ to $$$j$$$ of length 2. When adding an edge $$$u \to v$$$, first update $$$g$$$ in $$$O(n)$$$ time by going over which edge precedes or follows the edge just added. Then:

• If $$$u \neq 1$$$: Updating $$$f(x, 1)$$$ and $$$f(x, 2)$$$ is trivial. For updating $$$f(x, 3)$$$, either the added edge is the second edge in the shortest path (in which case we enumerate the next edge in $$$O(n)$$$ time), or the third edge (in which case we update using $$$f(u, 2)$$$). For $$$f(x, 4)$$$, either the added edge is the fourth edge in the shortest path (in which case we update using $$$f(u, 3)$$$), or the second or third edge (in which case we know the middle vertex $$$k$$$ of the 4-edge path, so we can update $$$f(x, 4)$$$ in constant time for each $$$x$$$ using $$$g(1, k)$$$ and $$$g(k, x)$$$). These updates take $$$O(n)$$$ time.
• If $$$u = 1$$$: We recalculate $$$f$$$ from scratch using the obvious $$$O(n^2)$$$ algorithm.

Since there are $$$O(n^2)$$$ edges of the first kind and $$$O(n)$$$ edges of the second, and extracting the final answer from the two "halves" takes $$$O(n)$$$ time per query, the final complexity is $$$O(n^3)$$$.

Interpret the problem as a graph with cows as vertices and friendships as edges.

Main Lemma: Two vertices $$$u$$$ and $$$v$$$ will become friends at some point iff there exists a path from $$$u$$$ to $$$v$$$ such that the ID of all vertices on the path (except endpoints) is less than $$$\min(u, v)$$$.

Proof: Suppose such a path exists. Note that all the non-endpoint vertices on the path will be deleted before either $$$u$$$ or $$$v$$$ is. Consider the deletion of a single vertex $$$w$$$. If $$$w$$$ is not on the path, the path remains valid. If $$$w$$$ is on the path, after deleting it the two vertices adjacent to $$$w$$$ on the path are now adjacent, so $$$w$$$ can be deleted from the path while keeping the path valid, shrinking its length by 1. Eventually, after every internal vertex on the path is deleted, the path would reach a length of 1, i.e. become a direct edge between $$$u$$$ and $$$v$$$, as desired.

Conversely, suppose no such path exists. Then after deleting a vertex with ID less than $$$\min(u, v)$$$, no new path satisfying the condition could possibly be formed (since the deletion only lets us bypass a low-ID vertex, but we need to bypass high-ID vertices to form such a path). Ultimately, vertex $$$\min(u, v)$$$ will be deleted, with no path satisfying the condition (and therefore no direct edge between $$$u$$$ and $$$v$$$) ever existing. $$$\square$$$

Now, for each $$$u$$$, we will count the number, $$$f(u)$$$, of $$$v \gt u$$$ such that the edge $$$(u, v)$$$ will eventually be formed; subtracting $$$m$$$ from the sum of this quantity over all $$$u$$$ gives the final answer. To do that, insert the vertices into the graph one by one by increasing order of ID. For each connected component, maintain the set of vertices adjacent to the component that has not been inserted into the graph yet, using, say, std::set (note that after inserting the first $$$u$$$ vertices, $$$f(u)$$$ is just the number of elements in the set for the connected component $$$u$$$ belongs in). Using small-to-large merging on these sets, the problem can be solved in $$$O(n \log^2 n)$$$ time.

Consider a single interval for which we want to compute the number of swaps needed.

Suppose that there are an even number of H's in it. Then the first H will be paired up with the last H, the second with the second-to-last, and so on. To align the first pair of H's, the number of swaps needed is twice the distance between the midpoint of the two H's and the midpoint of the whole interval (taking "half-positions" into account). The answer for the interval is just the sum over all pairs of H's. The case for an odd number of H's is similar, except that there is also a middle H to deal with and that it is possible that the task is impossible if the length of the interval is even.

Let's calculate the contribution of the intervals with an even number of H's. Enumerate the middle pair (of adjacent H's) and expand outward, one pair of H's at a time. Then, for a fixed set of pairs, the number of swaps is a function of the midpoint of the interval, and it is a piecewise linear function (sum of absolute value functions, one per pair), which can be maintained with Fenwick tree. Then for each interval corresponding to this set of pairs, we can evaluate this function at the midpoint in $$$O(\log n)$$$ time. The total complexity is $$$O(n^2 \log n)$$$ since each interval is processed once.

Handling the intervals with an odd number of H's is similar, but we enumerate the center H instead of the center pair, and we also have to check for each interval whether the task is possible.