（线段树/贪心）AtCoder Regular Contest 080 E : Old Maid

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

用下标从0开始的数组记录数，显然最终能作为开头的一定是下标为偶数的。由于是字典序，很容易想到贪心的想法，即从第一位开始，每一位取尽可能小的。暴力寻找最小的会使整个算法为n^2，复杂度过大，故采用线段树进行优化，维护区间奇数下标、偶数下标的数的最小值，使复杂度降到nlogn。

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <set>
  6 #include <map>
  7 #include <string>
  8 #include <cstring>
  9 #include <stack>
 10 #include <queue>
 11 #include <cmath>
 12 #include <ctime>
 13 #include <utility>
 14 using namespace std;
 15 #define REP(I,N) for (I=0;I<N;I++)
 16 #define rREP(I,N) for (I=N-1;I>=0;I--)
 17 #define rep(I,S,N) for (I=S;I<N;I++)
 18 #define rrep(I,S,N) for (I=N-1;I>=S;I--)
 19 #define FOR(I,S,N) for (I=S;I<=N;I++)
 20 #define rFOR(I,S,N) for (I=N;I>=S;I--)
 21 typedef unsigned long long ull;
 22 typedef long long ll;
 23 //const int INF=0x3f3f3f3f;
 24 const int INF=1e9;
 25 const ll INFF=0x3f3f3f3f3f3f3f3fll;
 26 const ll M=1e9+7;
 27 const ll maxn=1e5+7;
 28 const int MAXN=1005;
 29 const int MAX=2e5+5;
 30 const int MAX_N=MAX;
 31 const ll MOD=1e9+7;
 32 //const double eps=0.00000001;
 33 //ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
 34 template<typename T>inline T abs(T a) {return a>0?a:-a;}
 35 inline ll powMM(ll a,ll b){
 36     ll ret=1;
 37     a%=M;
 38 //    b%=M;
 39     while (b){
 40         if (b&1) ret=ret*a%M;
 41         b>>=1;
 42         a=a*a%M;
 43     }
 44     return ret;
 45 }
 46 int mina[MAX<<2][2];
 47 int a[MAX],lo[MAX],n;
 48 void init(int l,int r,int k)
 49 {
 50     mina[k][0]=mina[k][1]=INF;
 51     if(l==r)
 52         return;
 53     init(l,(l+r)/2,2*k);
 54     init((l+r)/2+1,r,2*k+1);
 55 }
 56 void build(int l,int r,int k)//左闭右闭
 57 {
 58     if(l==r)
 59     {
 60         scanf("%d",&a[l]);
 61         lo[a[l]]=l;
 62         mina[k][l%2]=a[l];return;
 63     }
 64     int mid=(l+r)/2;
 65     build(l,mid,2*k);
 66     build(mid+1,r,2*k+1);
 67     mina[k][0]=min(mina[2*k][0],mina[2*k+1][0]);
 68     mina[k][1]=min(mina[2*k][1],mina[2*k+1][1]);
 69 }
 70 int query(int ql,int qr,int l,int r,int k,int st)
 71 {
 72     if(l>=ql&&r<=qr)
 73         return mina[k][st];
 74     int mid=(l+r)/2;
 75     if(mid<ql)
 76         return query(ql,qr,mid+1,r,2*k+1,st);
 77     else if(mid>=qr)
 78         return query(ql,qr,l,mid,2*k,st);
 79     else
 80         return min(query(ql,qr,l,mid,2*k,st),query(ql,qr,mid+1,r,2*k+1,st));
 81 }
 82 struct node
 83 {
 84     int l,r,xiao,status;
 85     bool operator <(node b)const
 86     {
 87         return xiao>b.xiao;
 88     }
 89     node(int x=0,int y=0,int z=0,int s=0):l(x),r(y),xiao(z),status(s){}
 90 };
 91 priority_queue<node>que;
 92 int an[MAX],cnt;
 93 int main()
 94 {
 95     cnt=0;
 96     scanf("%d",&n);
 97     init(0,n-1,1);
 98     build(0,n-1,1);
 99     node tem;
100     tem.l=0;tem.r=n-1;tem.xiao=query(0,n-1,0,n-1,1,0);tem.status=0;
101     que.push(tem);
102     while(!que.empty())
103     {
104         tem=que.top();que.pop();
105         int now=lo[tem.xiao];
106         int nxt=query(now+1,tem.r,0,n-1,1,1^tem.status);
107         int to=lo[nxt];
108         an[cnt++]=tem.xiao;an[cnt++]=nxt;
109         if(now>tem.l)
110             que.push(node(tem.l,now-1,query(tem.l,now-1,0,n-1,1,tem.status),tem.status));
111         if(to-now>1)//中间的区间奇偶性会变化
112             que.push(node(now+1,to-1,query(now+1,to-1,0,n-1,1,tem.status^1),tem.status^1));
113         if(tem.r>to)
114             que.push(node(to+1,tem.r,query(to+1,tem.r,0,n-1,1,tem.status),tem.status));
115     }
116     for(int i=0;i<cnt;i++)
117         printf("%d ",an[i]);
118     return 0;
119 }