AtCoder Regular Contest 080 (ARC080) E

Regular Contest 080 (ARC080) E"/>

AtCoder Regular Contest 080 (ARC080) E

原文链接.html

题目传送门 - ARC080 E - Young Maids

题意

　　给定一个长度为$n$的序列$p$，$p$为$1\cdots n$的一个排列。

　　现在让你每次取出序列$p$的相邻两个，然后把他们按照原来的顺序放进序列$q$的最前面。注意每次这样的操作之后，$p$序列的剩余两半都会合并起来。

　　不断进行上述操作，直到$p$为空。

　　最小化序列$q$的字典序，并输出序列$q$。

　　$n\leq 2\times 10^5$

题解

　　这题就是随便贪心几下嘛。

　　定义下标为奇数的项叫做奇项，下标为偶数的项叫做偶数项。

　　我们考虑倒着还原原序列。

　　这样可以便于我们取最小字典序。

　　首先，考虑我们最后一次选择的项的下标在原序列中为$i,j$，那么在这之前，区间$[1,i),(i,j),(j,n]$不可能有相邻项。

　　于是在最后一次操作之前，这三个区间之间不可能发生跨区间的操作，那么这三个区间的大小显然都是偶数。

　　那么，我们考虑如何最小化开头两个数。

　　显然，我们先在全局找一个值最小的奇项$i$，然后在$(i,n]$中找一个值最小的偶项$j$。

　　然后成功把全局划分成$3$个区间。这个时候如果你去递归，说明你可能没睡好。

　　我是测完样例才发现错了

　　显然，虽然没有跨区间的操作，但是这些区间之间的操作是可以交替进行的。

　　于是我们每次都要找最小的。然后每次都会继续划分子序列，这样会使候选序列中多出一些来。

　　于是我们需要一个堆来维护最小值。

　　至于求奇偶项的最小值，只需要在开始的时候写个线段树就可以了。

　　然后我再一次的把$set$当堆用了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=200005;
int n,a[N],t[2][N<<2];
void update(int o,int rt,int L,int R,int pos){if (a[pos]<a[t[o][rt]])t[o][rt]=pos;if (L==R)return;int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;if (pos<=mid)update(o,ls,L,mid,pos);elseupdate(o,rs,mid+1,R,pos);
}
int query(int o,int rt,int L,int R,int xL,int xR){if (L>xR||R<xL)return 0;if (xL<=L&&R<=xR)return t[o][rt];int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;int Lans=query(o,ls,L,mid,xL,xR);int Rans=query(o,rs,mid+1,R,xL,xR);return a[Lans]<a[Rans]?Lans:Rans;
}
struct seg{int L,R,v;seg(){}seg(int _L,int _R){L=_L,R=_R,v=L>R?0:query(L&1,1,1,n,L,R);}friend bool operator < (seg A,seg B){return a[A.v]<a[B.v];}
};
int scnt=0;
set <seg> S;
int main(){scanf("%d",&n);a[0]=n+1;for (int i=1;i<=n;i++){scanf("%d",&a[i]);update(i&1,1,1,n,i);}S.clear();S.insert(seg(1,n));for (int i=1;i<=n/2;i++){seg now=*S.begin();S.erase(S.begin());int L=now.L,R=now.R;int Lmid=now.v,Rmid=query((Lmid&1)^1,1,1,n,Lmid,R);printf("%d %d ",a[Lmid],a[Rmid]);S.insert(seg(L,Lmid-1));S.insert(seg(Lmid+1,Rmid-1));S.insert(seg(Rmid+1,R));}return 0;
}

转载于:.html