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

4
3 2 4 1

Sample Output 1

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

2
1 2

Sample Output 2

1 2

---

Sample Input 3

8
4 6 3 2 8 5 7 1

Sample Output 3

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)

//题意：给出一个 p 序列，一个 q 序列，p 中有 1 -- n 的某种排列，q初始为空，现要求可以每次选两个相邻的数，移动到 q 中，要操作到 p 为空，并且要求 q 序列字典序最小

题解：相当难想到的一个题，假如有一个区间 l,r，肯定是，选择这区间内与 l 奇偶相同的，并且最小的作为开头，这样才能保证字典序最小，然后第二个数，应该为选的数右边的，并且与 l 奇偶性不同的，作为第二个，也要保证字典序最小，这部分是标准RMQ问题，随便用什么。然后，区间被分割成最多三块，用优先队列保存区间即可，排队顺序为区间内与左端点奇偶相同的位置上值小的先出队  n*lgn

还是难以想到啊，很好的题

# include
# include
# include
# include
# include
# include
# include
# include

# define eps 1e-
# define MOD
# define INF 0x3f3f3f3f
inline int Scan() {
int x=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-; ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();} return x*f; } inline void Out(int a) { if(a<) {putchar('-'); a=-a;} if(a>=) Out(a/);
putchar(a%+'');
}
const int MX=;
//Code begin….

int n;
int dat[MX];
int ans[MX];
int mn[MX];
int st[][MX][];
struct Qu
{
int l,r;
int dex; //zui xiao ,,biao hao
bool operator < (const Qu b) const{ return dat[dex]>dat[b.dex];
}
};
void Init()
{
mn[]=-;
dat[]=INF;
for (int i=;i<=n;i++)
{
if ((i&(i-))==) mn[i]=mn[i-]+;
else mn[i]=mn[i-];

     if (i&) st\[\]\[i\]\[\]=i;  
     else st\[\]\[i\]\[\]=i;  
 }

 for (int j=;(<<j)<=n;j++)  
 {  
     for (int i=;(i+(<<j)-)<=n;i++)  
     {  
         if (dat\[st\[\]\[i\]\[j-\]\]<=dat\[st\[\]\[i+(<<(j-))\]\[j-\]\])  
             st\[\]\[i\]\[j\] = st\[\]\[i\]\[j-\];  
         else  
             st\[\]\[i\]\[j\] = st\[\]\[i+(<<(j-))\]\[j-\];

         if (dat\[st\[\]\[i\]\[j-\]\]<=dat\[st\[\]\[i+(<<(j-))\]\[j-\]\])  
             st\[\]\[i\]\[j\] = st\[\]\[i\]\[j-\];  
         else  
             st\[\]\[i\]\[j\] = st\[\]\[i+(<<(j-))\]\[j-\];  
     }  
 }  

}
int st_cal(int l,int r,int same)
{
int k = mn[r-l+];
int c;
if (same) c=l%;
else c=(l+)%;

 if (dat\[st\[c\]\[l\]\[k\]\]<=dat\[st\[c\]\[r-(<<k)+\]\[k\]\])  
     return st\[c\]\[l\]\[k\];  
 else  
     return st\[c\]\[r-(<<k)+\]\[k\];  

}

int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++) dat[i] = Scan(); Init(); priority_queue Q;
Q.push((Qu){,n,st_cal(,n,)});
int pp=;
for (int i=;i<=n/;i++) { Qu now = Q.top();Q.pop(); int ml = now.dex; int mr = st_cal(ml+,now.r,); ans[pp++]=dat[ml]; ans[pp++]=dat[mr]; if (ml>now.l)
Q.push( (Qu){now.l,ml-,st_cal(now.l,ml-,)} );
if (mr->ml)
Q.push( (Qu){ml+,mr-,st_cal(ml+,mr-,)} );
if (mr<now.r)
Q.push( (Qu){mr+,now.r,st_cal(mr+,now.r,)} );
}
for (int i=;i<pp-;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[pp-]);
return ;
}