[??记录]AT2688 [ARC080C] Young Maids
command_block
2021-05-12 07:55:08
**题意** ： 给定 $n$ 元排列 $p = (p_1, p_2, ..., p_n)$. （保证 $n$ 为偶数）
根据下述步骤构造一个 $N$ 元排列 $q$。
首先，令 $q$ 为空。接下来，执行下述操作直到 $p$ 为空。
- 选择 $p$ 中两个相邻元素 ,按原顺序设它们是 $x,y$. 从 $p$ 中移除 $x,y$，将它们按顺序接在 $q$ 的**前面**。
求可能的形成的字典序最小的 $q$ 。
$2\times 10^5$ ，时限$\texttt{2s}$。
------------
观察我们最终拿出的对子有什么特征，不难发现，对子形成一个括号序列，且要从里到外拿取。
考虑最后一步如何操作。
尝试寻找一个最小的，能作为最外层左括号的位置，不难发现只需下标是奇数就可以了。
接着寻找一个最小的，与之配对的右括号。这需要早左括号右边，且下标为偶数。
（这两步可以用线段树或 ST 表）
确定这一对括号之后，我们将序列分为了三部分 ：
```cpp
...A... ( ...B... ) ...C...
```
这三部分的对子选取顺序是互不干扰的，故按照子问题处理。
处理完成后，我们得到了配对方案，以及对子之间的先后顺序（形如外向树）
在这个外向树上用堆贪心求出最小拓扑序列即可。
复杂度 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<queue>
#define Pr pair<int,int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back
#define MaxN 100500
using namespace std;
int lg2[MaxN];
struct ST
{
Pr t[18][MaxN];
void Init(int *x,int n){
for (int i=1;i<=n;i++)t[0][i]=mp(x[i],i);
for (int j=1;(1<<j)<=n;j++)
for (int i=1;i+(1<<j)-1<=n;i++)
t[j][i]=min(t[j-1][i],t[j-1][i+(1<<j-1)]);
}
Pr qry(int l,int r){
int k=lg2[r-l+1];
return min(t[k][l],t[k][r-(1<<k)+1]);
}
}T0,T1;
Pr s[MaxN];int tn;
vector<int> g[MaxN];
int solve(int l,int r)
{
int u=++tn;
if (l&1){
Pr tl=T1.qry((l+1)/2,(r+1)/2),
tr=T0.qry(tl.sec,r/2);
s[u]=mp(-tl.fir,tr.fir);
if (l<=tl.sec*2-2)g[u].pb(solve(l,tl.sec*2-2));
if (tl.sec*2<=tr.sec*2-1)g[u].pb(solve(tl.sec*2,tr.sec*2-1));
if (tr.sec*2+1<=r)g[u].pb(solve(tr.sec*2+1,r));
}else {
Pr tl=T0.qry(l/2,r/2),
tr=T1.qry(tl.sec+1,(r+1)/2);
s[u]=mp(-tl.fir,tr.fir);
if (l<=tl.sec*2-1)g[u].pb(solve(l,tl.sec*2-1));
if (tl.sec*2+1<=tr.sec*2-2)g[u].pb(solve(tl.sec*2+1,tr.sec*2-2));
if (tr.sec*2<=r)g[u].pb(solve(tr.sec*2,r));
}return u;
}
priority_queue< pair<Pr,int> >q;
int n,x0[MaxN],x1[MaxN],ans[MaxN<<1];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
if (i&1)scanf("%d",&x1[i/2+1]);
else scanf("%d",&x0[i/2]);
T0.Init(x0,n/2);T1.Init(x1,n/2);
lg2[1]=0;for (int i=2;i<=n/2;i++)lg2[i]=lg2[i>>1]+1;
int rt=solve(1,n);
q.push(mp(s[rt],rt));
tn=0;
while(!q.empty()){
int u=q.top().sec;q.pop();
ans[++tn]=-s[u].fir;ans[++tn]=s[u].sec;
for (int i=0;i<g[u].size();i++)
q.push(mp(s[g[u][i]],g[u][i]));
}
for (int i=1;i<=tn;i++)
printf("%d ",ans[i]);
return 0;
}
```