ABC413 : E Reverse 2^i

大致题意 ：

将一组数列用类似ST表的方式分开，相邻两个大小相同的块可以反转，问最小字典序

思路 ：

为了让字典序最小，我们肯定要先把1挪到最前，然后是2,3...   观察一下样例：

                                我们要先将1放在第一位，所以就将红块与绿块反转

再将黄块与蓝块反转

终于，1来到了第一位

根据上方的图可以看出，1如果要往不同的块走，就需要“绑架”它这个块中的数字一起走

而答案的输出，其实可以看作是先走左块还是右块

那为了让字典序最小，肯定就要先走包含的最小数更小的那一个啦，代码实现比较简单，主要就是ST表找最小值+dfs遍历

代码 ：

#include<bits/stdc++.h>
using namespace std;
int n,a[1100000],b[110000],st[1100000][31];
int ask(int l,int r)
{
	int k=log2(r-l+1); 
	return max(st[l][k],st[r-(1<<k)+1][k]);
}
void dfs(int l,int r)
{
	if(l==r)
	{
		printf("%lld ",a[l]);
		return;
	}
	int mid=(l+r)>>1;
	if(ask(l,mid)<ask(mid+1,r))
	{
		dfs(l,mid);
		dfs(mid+1,r);
	}
	else
	{
		dfs(mid+1,r);
		dfs(l,mid);
	}
}
void solve()
{
	scanf("%d",&n);
	for(int i=0;i<=20;i++) for(int j=0;j<=b[n];j++) st[j][i]=1e16;
	for(int i=1;i<=b[n];i++) scanf("%d",&a[i]),st[i][0]=a[i];
	for(int j=1;j<=21;j++)
	{
		for(int i=1;i+(1<<j)-1<=b[n];i++)
		{
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}   
	}
	dfs(1,b[n]);
	printf("\n");
}
int main()
{
	int t;
	scanf("%d",&t);
	b[0]=1;
	for(int i=1;i<=20;i++) b[i]=b[i-1]*2;
	while(t--)
	{
		solve();
	}
	return 0;
}