I use only a few thousand operations. I noticed that you can quickly reduce the problem from 1000 numbers to at most 20, by merging two numbers divided by the same power of two, you get two numbers which are divided by a strictly larger power of two (maybe one of the numbers ends up being zero). So, after this process is done, you can have at most 20 nonzero numbers left. Then, I solved the remainder by just reducing some triplet to two numbers, and I did this by just running a BFS on the search space — I hypothesised that I'll need $$$O(sum)$$$ steps on average and it turned out to be true. I didn't even optimize for visiting the same state twice.

I solved this by first constructing a list of "optimal segment sets", each one represents a subset of segments such that they are all colored zero or $$$c$$$ for some fixed $$$c$$$ and all their neighbors (segments which intersect them) are colored in the same way. For each such "optimal segment set", assign an interval $$$[L,R]$$$, so that $$$L$$$ is the left end of the leftmost segment in the subset, and $$$R$$$ is the right end of the rightmost of all segments and their neighbors, and a value $$$v$$$ — the number of segments and their neighbors — this will be the weight of the object. After finding these "optimal segment sets", run DP to find the largest total weight of a nonintersecting subset of these "optimal segment sets". Obviously you can't generate find "optimal segment sets" by taking all subsets. You can do this by fixing the leftmost taken segment and greedily picking the segments to the right of it sorted by their right end.

Yes, I'm aware this solution is hard to understand unless you really spend a lot of time on this problem.

Just like everyone else, I managed to squeeze an $$$O(nq)$$$ solution. I'm actually not even sure my solution is correct, I didn't prove it. Basically my solution is to create a pair of arrays where both bears and horses are sorted in increasing order, then doing DP where the array is split into groups of size 1, 2 and 3, and where inside each group you have to match bears to horses within the group. I have no idea why this works. The actual solution in $$$O(q \log n)$$$ would be, of course, to put this same algorithm inside a segment tree using standard semigroup theory.

My solution is based on an algorithm which, given two arrays $$$a,b$$$ containing unique elements, each of size at most $$$k$$$, returns two arrays $$$a'$$$ and $$$b'$$$ such that $$$a'$$$ is a subset of $$$a$$$, $$$b'$$$ is a subset of $$$b$$$, they don't intersect, and together they contain all the unique elements from $$$a,b$$$. The algorithm takes at most $$$3k$$$ steps. First, you query all elements of $$$a$$$, then, all elements of $$$b$$$, then $$$2k+1 - |a| - |b|$$$ times query the last element of $$$b$$$ (we'll call these filler queries), then, the first $$$|a| - k - 1 + |b|$$$ elements of $$$a$$$. Finally, reset the memory. Each time you query an element (except for filler queries) and you got "Y" as a reply, mark the element as removed. Then $$$a',b'$$$ are simply the non-removed elements. Can you see why this algorithm works? I have the proof but won't write it here.

The solution is then to divide the input array into $$$n/k$$$ groups of size $$$k$$$, for each group find the unique elements by just asking each of them once and resetting, then applying the algorithm above for each pair of groups. It can be shown that at most $$$\frac{3n^2}{2k}-\frac{n}{2}$$$ queries (except resets) are used.

Let $$$W=10^8$$$ and $$$B=3200$$$, notice that $$$B$$$ divides $$$W$$$. First we'll ask all points $$$(x,x)$$$ such that $$$B$$$ divides $$$x$$$ and $$$-W\leq x \leq W$$$. There will be exactly $$$62501$$$ queries. Take the point with the largest answer and call it $$$(q,q)$$$. It can be shown that this largest answer will be at least $$$3200$$$. You will use this large space in both $$$x$$$ and $$$y$$$ directions to find all horizontal lines. Just walk greedily through the range $$$[-W,W]$$$ and set $$$x=q$$$ in all queries. This will use at most approx. $$$182500$$$ queries. To find all vertical lines, use the information you already have about horizontal lines and run a recursive parallel binary search in the middle of the largest horizontal strip, to maximize the step size. I have no idea how many steps this phase uses but it seems to fit comfortably into the constraints.