I got a full score for sladoled, but I suspect it was not the intended solution. Firstly, it's clear that each stand can be solved separately. Keep a boolean array of which flavours can be achieved, and as each scoop is delivered, do a sweep through the array to update it in the usual way. To get that from partial to a complete score, I optimised it using bit packing, updating 64 bits at a time. That is more complex when b < 64, so I

1. added a special code-path for that case, which handles propagation within a single 64-bit word using binary lifting;
2. added an early-out so that if a scoop is delivered which can already be made as a sum of other scoops, the array is not updated at all.

The latter limits the number of times the more complex code-path is needed to O(64N).

For Magija

My solution for $$$O(nlog^2(n))$$$ is to merge components just like in $$$O(nq)$$$ solution but here we want to merge elements that come from different components.

Let's see how to check if merging $$$[a, a+x]$$$ and $$$[b, b+x]$$$ changes anything. Let's have an array $$$d$$$ where $$$d_i$$$ shows a representative of union where $$$i$$$ is. Here we want to check if the corresponding substrings of $$$d$$$ are same. To do that we compare their hashes.

Now se can check what positions differ in substrings by binary searching them. To quickly get hashes of substrings of $$$d$$$ we use segment tree. When merging two components we need to update the array $$$d$$$. Iterate over elements in smaller component and change $$$d$$$ on those positions and update the segment tree. That's $$$O(n log(n))$$$ changes in total, with a time $$$O(log(n))$$$ complexity each. Obtaining a position that differs with binary search + segment tree is $$$O(log^2(n))$$$.

So that is $$$O(n log^2(n))$$$ in total.

That's roughly what I wrote initially but it TL'ed. I suspect the difference may be the if (bs[a][b]) break; which I didn't have.

still waiting