AtCoder Beginner Contest 413 补题

AtCoder Beginner Contest 413

Reverse 2^i

想要让字典序最小，那么需要通过旋转操作将小的数字提到前面去，数组可以被划分为2的幂次的区间，优先处理小的区间，因为对于大的区间无法比较判断是否要交换。

对于一个区间，将其分为左右两部分，此时的做有区间已经是保证字典序最小的了，关键在于如何比较这两个区间是否需要通过旋转操作变得更小，因为旋转操作不限，那么可以直接比较两个区间的首部元素，然后直接交换，等价于将左右两个数组旋转后再旋转。

for _ in range(R()):
    n=R()
    nums=RR()
    # 从小到大枚举
    for i in range(1,n+1):
        l,r=0,(1<<i)-1
        while r<len(nums):
            mid=(l+r)>>1
            # 比较首部元素
            if nums[l]>nums[mid+1]:
                nums[l:mid+1],nums[mid+1:r+1]=nums[mid+1:r+1],nums[l:mid+1]
            l=r+1
            r=l+(1<<i)-1

    print(*nums)