Subset of Master Shifu

The key factor of the problem is, only the first $6$ elements of the array will be updated at most. The rest of the array will be fixed always. Let's use the concept of "meet in the middle" here. We will split the array into two parts. But we won't split the array equally like "meet in the middle". We'll split the array such that the first $min(N,6)$ elements remain in one part and the other part contains the rest of the elements of the array that will never change (this other part can be empty too if $N\leq6$). Let's call the first part "prefix part" and the other part "suffix part". Also, let's assume, the subsets generated from the prefix part are "prefix subsets", the subsets generated from the suffix part are "suffix subsets" and the subsets containing both of the elements from the prefix part and the suffix part are "prefix-suffix subsets". Note that, it is assumed that all of the subsets are lexicographically ordered.

Suffix subsets will always be after prefix subsets and prefix-suffix subsets in lexicographical order. It can also be easily observed that if we insert a fixed subset at the beginning of some lexicographically ordered subsets, the order will still be correct. So, it can be used to get the order of prefix-suffix subsets. To generate lexicographical ordering, we can traverse like a binary tree where level $i$ represents the $i^{th}$ element. The left child and right child of $(i-1)^{th}$ level's nodes means $i^{th}$ element is "taken" and "not taken" respectively. The level of the root is $0$ which means an empty subset. Let's see an example for an array of size $3$ where $1^{st}$ two elements are considered in the prefix part and the $3^{rd}$ element is considered in the suffix part:

The green box up the nodes contains the prefix subsets represented by the nodes. The blue box contains the prefix-suffix subsets that start with the prefix subset of that node. The green nodes mean a new element is taken here and in red nodes, there is no new element taken. Now, if we write down the prefix subsets of each node in preorder traversal and prefix-suffix subsets of each node in postorder traversal together ignoring the red nodes' subsets, the order of the subsets will be: $\{1\}, \{1,2\}, \{1,2,3\}, \{1,3\}, \{2\}, \{2,3\}$. This is actually the lexicographical ordering of the subsets if we write down all the prefix and prefix-subsets together. Suffix subset generation is exactly as same as prefix subset generation.

As the prefix part has at most $6$ elements, the number of non-empty prefix subsets will be at most $2^6-1=63$ which is small enough to be generated in each query. But the number of prefix-suffix subsets and suffix subsets can be large enough that generating them in each query will cause a "Time Limit Exceed" verdict. So, what can we do now?

At first, let's observe a property of the $K^{th}$ element. The $K^{th}$ element of an array is actually the smallest element $M$ such that the number of elements smaller or equal to $M$ is at least $K$. For the $K^{th}$ element of $[L,R]$ range, we just need to apply the property in $[L,R]$ range instead of the whole array. We can run a binary search to find the smallest such $M$. For each mid-value $m$, we just need to count how many numbers are smaller or equal to $m$.

To count them, for prefix subsets, we can generate each of them and compare the values with $m$ if the subset lies in $[L,R]$ range. For suffix subsets, we need to manage a data structure (setter used "Persistent Segment Tree") that can answer fastly how many numbers are smaller or equal to $m$ in a range. After finding out the range of the suffix subsets that lie in $[L,R]$ range, we just need to perform a range query on that data structure. Note that, as the numbers can be very large they can be mapped to their sorted order while managing the data structure. For example, the array $\{78, 12, 67\}$ can be mapped to $\{3, 1, 2\}$ array and used accordingly.

For prefix-suffix subsets, to get the desired count from them, we need to do something trickily. For each prefix subsets, we need to find out the range of suffix subsets that lie in $[L,R]$ range if that prefix subset is inserted at the beginning of the suffix subsets. After that, the range query operation is quite similar to the range query operation applied on suffix subsets before. The only difference is, we also need to take care of the prefix subset's value here.

In the update operations, we just need to change the value of the corresponding index in the main array.

Complexity: For each of the second types of queries, $O(\log_2(M)\times 2^{B}\times \max(1,\log_2(2^{N-B})) ) \approx O(\log_2(M)\times 2^{B}\times\max(1,N-B) )$, where $B(B\geq6)$ is the size of the prefix part. Taking $B=6$ is enough in this problem.

Setter's Solution: https://ideone.com/rP08FL