题解：[ABC413E] Reverse 2^i

· · 题解

首先你会发现可以翻转的区间类似线段树，大致长这样：

然后你发现，说是翻转，不如说是交换。

具体的，设有区间 [l, mid] 和 [mid + 1, r] 可以执行操作，其中 mid = ⌊\frac{l + r}{2}⌋。那么可以通过操作交换两个区间。
因为可以先操作 [l, r]，再分别操作两个区间。

到此，这题基本就结束了。利用分治的思想排序即可。

具体的，如果 l \ge r 就直接结束。否则递归 [l, mid] 和 [mid + 1, r]，其中 mid = ⌊\frac{l + r}{2}⌋。如果 a_l > a_{mid + 1}，则交换 [l, mid] 和 [mid + 1, r]。

时间复杂度 O(2^nn)。

Submission