AtCoder Regular Contest 080 E：Young Maids

Contest 080 E：Young Maids"/>

AtCoder Regular Contest 080 E：Young Maids

题目传送门：

题目翻译

给你一个\(n\)的排列\(p\)，一个空序列\(q\)，你每次可以从\(p\)里选择相邻的两个元素按照原本的顺序放在\(q\)的首位。问可以得到的排列字典序最小是什么。长度小于等于\(2*10^5\)

题解

我们考虑倒着做。看看能最后一个被取出来的数最小是什么。显然，能在最后一对被取出来的数对第一个数在奇数位，第二个数在偶数位。

我们可以对奇数位的数字维护一个\(st\)表，偶数也维护一个。每次取出这一对数之后，就把当前区间分成了\([l,pos-1],[pos+1,tmp-1],[tmp+1,r]\)三段，其中中间一段数对的奇偶性要改变，然后递归去做就可以了。

最后拓扑加堆输出答案。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
#define fr first
#define sc secondconst int maxn=2e5+5;pii node[maxn];
int n,rt,tot,cnt;
int f[20][maxn][2];
int a[maxn],now[maxn],pre[maxn],son[maxn];int read() {int x=0,f=1;char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';return x*f;
}void add(int a,int b) {if(!b)return;pre[++tot]=now[a];now[a]=tot,son[tot]=b;
}int cmp(int pos1,int pos2) {if(a[pos1]<a[pos2])return pos1;return pos2;
}void make_st() {for(int i=1;i<20;i++)for(int j=1;j+(1<<i)-1<=n;j++)for(int k=0;k<2;k++)f[i][j][k]=cmp(f[i-1][j][k],f[i-1][j+(1<<(i-1))][k]);
}int solve(int l,int r,int opt) {if(r<l)return 0;if(l+1==r) {node[++cnt]=make_pair(a[l],a[r]);return cnt;}int x=log2(r-l+1);int pos=cmp(f[x][l][opt],f[x][r-(1<<x)+1][opt]);x=log2(r-pos+1);int tmp=cmp(f[x][pos][opt^1],f[x][r-(1<<x)+1][opt^1]);node[++cnt]=make_pair(a[pos],a[tmp]);x=cnt;add(x,solve(l,pos-1,opt));add(x,solve(pos+1,tmp-1,opt^1));add(x,solve(tmp+1,r,opt));return x;
}struct Heap {int len;int tree[maxn];void ins(int u) {tree[++len]=u;int pos=len;while(pos>1) {if(node[tree[pos]]<node[tree[pos>>1]])swap(tree[pos],tree[pos>>1]),pos>>=1;else break;}}int pop() {int res=tree[1];tree[1]=tree[len--];int pos=1,son=2;while(son<=len) {if(son<len&&node[tree[son|1]]<node[tree[son]])son|=1;if(node[tree[son]]<node[tree[pos]])swap(tree[pos],tree[son]),pos=son,son=pos<<1;else break;}return res;}
}H;void make_ans() {H.ins(rt);while(H.len) {int u=H.pop();printf("%d %d ",node[u].fr,node[u].sc);for(int p=now[u];p;p=pre[p])H.ins(son[p]);}
}int main() {n=read();a[0]=2e9;for(int i=1;i<=n;i++)a[i]=read(),f[0][i][i&1]=i;make_st();rt=solve(1,n,1);make_ans();return 0;
}

转载于:.html