Weird that City was solved only by 19 people, it is quite simple.

For Queries, naive solution passed 50% of tests, I was surprised for 10¹⁰ to pass. (though TL was quite large, 4 seconds). And that "solved by 220" was really confusing.

Segments is nice, I liked it.

For Triangle — why give a wrong formula?..

I use a trie on my solution. Suppose queries are in the form 1..R instead of L..R. You can answer queries by increasing R mantaining a trie with all the bitstrings from a[1..R]. Bitstrings will be added as usual, starting from most significant bits (you should make all the strings the same length. 20 is enough in this case). When you a got a bitstring X, you can find a bitstring Y in that trie that gives maximum in the following way:

1. find Y from the most significant to the least significant bit.
2. when processing the i-th bit, if there's some outgoing edge !X_i from current trie node, take it (that's because you are greedily maximizing the most significant bits).
3. take X_i otherwise.

Problem here is that you are given L..R queries. To avoid ending up with a Y that does not lie on this segment, you can mantain a max_idx value on every node of the trie. max_idx of a node is the maximum index (on the original array) of a bitstring which ends on the subtree of this node. Given this, you can always take transitions which guarantees you that you will end up with a valid Y.

1. when processing the i-th bit, if there's some outgoing edge !X_i from current node and the next node max_idx ≥ L, take it.
2. take X_i otherwise.

Time Complexity: O(nlogmax(A_i))