AtCoder 2688 Young Maids

AtCoder 2688 Young Maids"/>

AtCoder 2688 Young Maids

E - Young Maids

---

Time limit : 2sec / Memory limit : 256MB

Score : 800 points

Problem Statement

Let N be a positive even number.

We have a permutation of (1,2,…,N), p=(p1,p2,…,pN). Snuke is constructing another permutation of (1,2,…,N), q, following the procedure below.

First, let q be an empty sequence. Then, perform the following operation until p becomes empty:

• Select two adjacent elements in p, and call them x and y in order. Remove x and y from p (reducing the length of p by 2), and insert x and y, preserving the original order, at the beginning of q.

When p becomes empty, q will be a permutation of (1,2,…,N).

Find the lexicographically smallest permutation that can be obtained as q.

Constraints

• N is an even number.
• 2≤N≤2×105
• p is a permutation of (1,2,…,N).

---

Input

Input is given from Standard Input in the following format:

N
p1 p2 … pN

Output

Print the lexicographically smallest permutation, with spaces in between.

---

Sample Input 1

Copy

4
3 2 4 1

Sample Output 1

Copy

3 1 2 4

The solution above is obtained as follows:

p	q
(3,2,4,1)	()
↓	↓
(3,1)	(2,4)
↓	↓
()	(3,1,2,4)

---

Sample Input 2

Copy

2
1 2

Sample Output 2

Copy

1 2

---

Sample Input 3

Copy

8
4 6 3 2 8 5 7 1

Sample Output 3

Copy

3 1 2 7 4 6 8 5

The solution above is obtained as follows:

p	q
(4,6,3,2,8,5,7,1)	()
↓	↓
(4,6,3,2,7,1)	(8,5)
↓	↓
(3,2,7,1)	(4,6,8,5)
↓	↓
(3,1)	(2,7,4,6,8,5)
↓	↓
()	(3,1,2,7,4,6,8,5)

题目大意：有一列数，每次选择相邻的两个数取出，并插入在一个新数列里，求最后新数列字典序最小的方案。

思路：比较容易思考的一种贪心策略，我们一定是从小往大拿，但是我们很难判断最小的可拿的是哪个。再经过观察我们可以发现，初始数列位置的奇偶性决定了最终位置的奇偶性，每次取出后会把数列分成几个部分，我们只要一个部分一个部分的考虑即可。问题就被转化成了求区间最值问题。可以使用线段树或者ST表。因为ST表比较容易写跪我线段树比较熟练，我就选择写了线段树。我们把所有分割成的区间放在一个堆里，每次取起点最小的区间开始查询即可。我们需要用到重载<操作。

代码。

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>using namespace std;const int MAXN=2e5;
const int INF=1e9;
struct node
{int x,y,l,r;friend bool operator <(const node a,const node b){return a.x>b.x;}
};
priority_queue <node> ans;
int f[4*MAXN][2]; 
int a[MAXN],id[MAXN]; 
void build(int root,int left,int right)
{if (left==right){if (left&1){f[root][1]=a[left],f[root][0]=INF; }else{f[root][0]=a[left],f[root][1]=INF;}return ;}int mid=(left+right)>>1;build(2*root,left,mid);build(2*root+1,mid+1,right);f[root][1]=min(f[2*root][1],f[2*root+1][1]);f[root][0]=min(f[2*root][0],f[2*root+1][0]); 
}	
int query(int root,int left,int right,int qleft,int qright,bool p)
{if (left>=qleft && right<=qright){if (p){return f[root][1];}else{return f[root][0];}}int mid=(left+right)>>1;if (qright<=mid){return query(2*root,left,mid,qleft,qright,p);}else if (qleft>mid){return query(2*root+1,mid+1,right,qleft,qright,p);}else{int ans1,ans2;ans1=query(2*root,left,mid,qleft,mid,p);ans2=query(2*root+1,mid+1,right,mid+1,qright,p);return min(ans1,ans2);}
}int main()
{int n;scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&a[i]);id[a[i]]=i;}build(1,1,n);int x=query(1,1,n,1,n,1);int y=query(1,1,n,id[x]+1,n,0);node q;q.l=1,q.r=n,q.x=x,q.y=y;ans.push(q);for (int i=2;i<=n/2;i++){q=ans.top();ans.pop();int nx=id[q.x];int ny=id[q.y];node now;if (q.l<nx){bool p=q.l&1;int x=query(1,1,n,q.l,nx-1,p);int y=query(1,1,n,id[x]+1,nx-1,p^1);now.l=q.l;now.r=nx-1;now.x=x;now.y=y;ans.push(now);}if (nx+1<ny){bool p=(nx+1)&1;int x=query(1,1,n,nx+1,ny-1,p);int y=query(1,1,n,id[x]+1,ny-1,p^1);now.l=nx+1;now.r=ny-1;now.x=x;now.y=y;ans.push(now);}if (ny<q.r){bool p=(ny+1)&1;int x=query(1,1,n,ny+1,q.r,p);int y=query(1,1,n,id[x]+1,q.r,p^1);now.l=ny+1;now.r=q.r;now.x=x;now.y=y;ans.push(now);}printf("%d %d ",q.x,q.y);}while (!ans.empty()){node now=ans.top();ans.pop();printf("%d %d ",now.x,now.y);}return 0;
}