一道挺有意思的题目，在这里记录一下。
题目大意
给你一个长度为 (n) 的排列，每一次你可以取出相邻的两个数将其放在答案序列的开头，最后问你字典序最小的答案序列是什么。
题解
由于最后是求字典序最小，所以我们肯定需要倒序求解，所以我们需要考虑如何取才能使得剩下的序列合法。
如果我们在区间 ([L,R]) 当前选择点 (l) 和点 (r) ，那么最后的区间很显然会被我们分成三部分， ([L,l-1]) ， ([l+1,r-1]) 和 ([r+1,R]) 。而且这三个区间的长度必须为偶数才可以满足区间同时也可分。我们就可以用一个优先队列来模拟一下，每一次取出当前所以区间中可以选择字典最小的点对的区间，再将其拆分为三个区间。不断重复此操作直到最后所有的数都被取出即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,a[N],b[N];
struct Point{int data,loc;};
bool operator < (const Point a,const Point b){return a.data<b.data;}
struct Seg_Tree
{
struct Node{Point data;}tr[N<<2];
void up(int u){tr[u].data=min(tr[u<<1].data,tr[u<<1|1].data);}
void build(int u,int l,int r,int a[])
{
if(l==r)
{
tr[u].data.data=a[l];
tr[u].data.loc=l;
return ;
}
int mid=(l+r)>>1;
build(u<<1,l,mid,a);
build(u<<1|1,mid+1,r,a);
up(u);
}
void chg(int u,int l,int r,int x)
{
if(l==r){tr[u].data.data=1e9+7;return ;}
int mid=(l+r)>>1;
if(x<=mid) chg(u<<1,l,mid,x);
else chg(u<<1|1,mid+1,r,x);
up(u);
}
Point query(int u,int l,int r,int x,int y)
{
if(x<=l&&r<=y) return tr[u].data;
int mid=(l+r)>>1;Point res={1000000007,0};
if(x<=mid) res=min(res,query(u<<1,l,mid,x,y));
if(y>mid) res=min(res,query(u<<1|1,mid+1,r,x,y));
return res;
}
}t[2];//0为偶，1为奇
struct Data{int l,r;Point data;};
bool operator < (const Data a,const Data b){return a.data.data>b.data.data;}
priority_queue<Data> q;
vector<int> res;
int main()
{
cin>>n;
for(int i=1,x;i<=n;++i)
{
scanf("%d",&x);
if(i&1) a[i]=1e9+7,b[i]=x;
else a[i]=x,b[i]=1e9+7;
}
t[0].build(1,1,n,a);
t[1].build(1,1,n,b);
Data tmp;
tmp.l=1,tmp.r=n;
tmp.data=t[1].query(1,1,n,1,n);
q.push(tmp);
for(int i=1;i<=n/2;++i)
{
tmp=q.top(),q.pop();
int tag=tmp.l%2;
// printf("%d
",tag);
Point L=tmp.data,R=t[tag^1].query(1,1,n,L.loc+1,tmp.r);
// printf("%d %d %d %d
",tmp.l,tmp.r,L.data,R.data);
res.push_back(L.data),res.push_back(R.data);
Data now;
now.l=tmp.l,now.r=L.loc-1;
if(now.l<=now.r)
{
now.data=t[tag].query(1,1,n,now.l,now.r);
q.push(now);
}
now.l=L.loc+1,now.r=R.loc-1;
if(now.l<=now.r)
{
now.data=t[tag^1].query(1,1,n,now.l,now.r);
q.push(now);
}
now.l=R.loc+1,now.r=tmp.r;
if(now.l<=now.r)
{
now.data=t[tag].query(1,1,n,now.l,now.r);
q.push(now);
}
}
for(int i=0;i<(int)res.size();++i) printf("%d ",res[i]);
printf("
");
return 0;
}