Constructing the Array
You are given an array a of length n consisting of zeros. You perform n actions with this array: during the i-th action, the following sequence of operations appears:
Choose the maximum by length subarray (continuous subsegment) consisting only of zeros, among all such segments choose the leftmost one;
Let this segment be [l;r]. If r-l+1 is odd (not divisible by 2) then assign (set) a[(l+r)/2]:=i (where i is the number of the current action), otherwise (if r-l+1 is even) assign (set) a[(l+r-1)/2]:=i.
The first line of the input contains one integer t (1≤t≤10^4) — the number of test cases. Then t test cases follow.
The only line of the test case contains one integer n (1≤n≤2⋅10^5) — the length of a.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5 (∑n≤2⋅10^5).
For each test case, print the answer — the array a of length n after performing n actions described in the problem statement. Note that the answer exists and unique.
Consider the array a of length 5 (initially a=[0,0,0,0,0]). Then it changes as follows: Firstly, we choose the segment [1;5] and assign a:=1, so a becomes [0,0,1,0,0]; then we choose the segment [1;2] and assign a:=2, so a becomes [2,0,1,0,0]; then we choose the segment [4;5] and assign a:=3, so a becomes [2,0,1,3,0]; then we choose the segment [2;2] and assign a:=4, so a becomes [2,4,1,3,0]; and at last we choose the segment [5;5] and assign a:=5, so a becomes [2,4,1,3,5].
We will use the heap data structure to solve this problem (we will use max heap), since the problem is to assign count variable i, we will create priority queue with pair, the first part of the pair is the size of subarray and the second part of the pair is another pair which contains indices l and r, left index and right index of the subarray.
A/c to the question if the size of the left and right subarray with the equal number of 0s in them we have to choose the left part, so to solve the problem we multiply the indexes with -1 so that left part is chosen.
While a priority queue is not empty, we pick the max element from the top of the priority queue and pop it from the priority queue.
Now, l=be the left index of the subarray and r be the right index of the subarray. We take the mid index as (l+r)/2 and fill it with cnt and increment it with one each time. If l==r then there is no possibility of partition among it so simply continue, else one part will be the subarray of l to mid-1 and the other part will be mid+1 to r with length (mid-l) and (r-mid) respectively.
Push them with their respective length and indices into the priority queue.
We repeat the process untill the priority queue is not empty.
Output:need an explanation for this answer? contact us directly to get an explanation for this answer