Let's begin by examining only the single-box case, with ~N = 1~. After the first cow opens the box, each cow should clearly choose to claim the most powerful remaining grenade on each of their turns. As such, if we consider sorting the grenade powers in non-increasing order, the second cow will end up getting all of the grenades which are at odd indices in the sorted list (the ~1^\text{st}~, ~3^\text{rd}~, etc.), while the first cow will get the ones at even indices. Therefore, we can compute the total grenade power received by each cow in ~\mathcal O(G_1 \log G_1)~ time. For future convenience, let's call the box's overall value the difference between the grenade power received by the second and first cows (note that this difference is always non-negative, as the second cow can't get less than the first cow).

Let's next consider how the grenade power received by the cows changes when a single grenade's power is increased or decreased by ~1~. If a certain value gets increased from ~x~ to ~x+1~, then we can find the value ~x~ in the sorted list (in ~\mathcal O(\log G_1)~ time using binary search) and increment it in place. If ~x~ appears multiple times in the list, let's specifically find the last occurrence and increment that one. Note that, after performing this operation, the whole list is guaranteed to still be sorted in non-increasing order, without needing to reorder any elements! This means that the box's overall value can easily be updated in another ~\mathcal O(1)~ time. A value getting decreased by ~1~ can be handled in a similar fashion.

We're now ready to consider what's going on in the entire game, when there are multiple boxes. Regarding the cows' overall strategy, it can be observed that once a cow opens a box, it's optimal for both cows to then only take grenades from that box until it becomes empty – it can never help a cow to instead choose to open some other box prematurely. Now, let's refer to boxes containing even numbers of grenades as even-boxes, and the others as odd-boxes. When a cow opens an even-box, an odd number of total turns will go by until it's been exhausted, meaning that the other cow will end up opening the next new box. On the other hand, when a cow opens an odd-box, it will once again be their turn after that box has been exhausted. As we've already seen, being forced to open a box is disadvantageous, so it's optimal for the cows to repeatedly choose all of the even-boxes to keep passing that disadvantage back and forth, until one cow gets stuck with opening all of the odd-boxes at the end of the game (which cow that will be depends only on the number of even-boxes).

Now that we know how the game will generally play out, we can consider how to compute its exact result. We should start by computing all of the boxes' initial overall values in ~\mathcal O(K \log K)~ time, where ~K~ is the total number of grenades in all of them. Furthermore, whenever a grenade inside box ~i~ gets swapped out, we can go ahead and independently update box ~i~'s overall value in ~\mathcal O(\log G_i)~ time, as shown above.

Past that, the odd-boxes are simple – a certain cow is known to be the one to open each of those, so the effects of an odd-box's overall value on the cows' grenade power totals for the entire game is clear, including handling when it gets updated.

As for the even-boxes, observe that the cows will take turns opening them, each time choosing the remaining one with the smallest overall value in order to minimize their disadvantage from having to open it. This is almost exactly the same situation as what happens to the grenades inside a single box! Therefore, we can apply the same approach of computing a sorted list of initial even-box overall values in ~\mathcal O(N \log N)~ time, and then maintain it as well as the game's overall value (the difference between the total grenade powers obtained by Bessie and Angus) in ~\mathcal O(\log N)~ time per update. Part of the reason this works out is that an individual absolute grenade power change of at most ~1~ results in its box's overall value also changing by at most ~1~.

The overall time complexity of this algorithm is ~\mathcal O(N \log N + K \log K + M \log(N+K))~, where ~K~ is the total number of grenades.