[arc080e]Young Maids

arc080e]Young Maids"/>

[arc080e]Young Maids

题目大意

一个长度为偶数的排列p，每次取出相邻两个数并从p中删除，然后将这两个数按顺序加入q的开头（q初始为空）。
问能得到最小字典序的q。

做法

在堆中保存若干个区间(l,r)，以及从中选出最小的和l奇偶性相同的位置u，以及在这个位置之后最小的和r奇偶性相同的位置v。记作(l,r,u,v)。
然后我们每次从堆中取出a[u]最小的(l,r,u,v)，并将u、v加至开头，然后把区间分裂成(l,u-1)(u+1,v-1)(v+1,r)再丢进堆里。
一个区间位置奇偶性为0/1的最小数所在位置可用RMQ找到，虽然我写了线段树。

#include<cstdio>
#include<algorithm>
#include<queue>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=200000+10,inf=1000000000;
int ans[maxn],tree[maxn*4][2],f[maxn];
int i,j,k,l,r,s,t,n,m,tot,top;
struct dong{int l,r,u,v;friend bool operator <(dong a,dong b){return f[a.u]>f[b.u];}
} zlt;
priority_queue<dong> heap;
void update(int p){int i,j,k;fo(i,0,1){j=tree[p*2][i];k=tree[p*2+1][i];if (f[j]<f[k]) tree[p][i]=j;else tree[p][i]=k;//tree[p][i]=min(tree[p*2][i],tree[p*2+1][i]);}
}
void build(int p,int l,int r){if (l==r){tree[p][l%2]=l;return;}int mid=(l+r)/2;build(p*2,l,mid);build(p*2+1,mid+1,r);update(p);
}
int query(int p,int l,int r,int a,int b,int c){if (l==a&&r==b) return tree[p][c];int mid=(l+r)/2;if (b<=mid) return query(p*2,l,mid,a,b,c);else if (a>mid) return query(p*2+1,mid+1,r,a,b,c);else{int j=query(p*2,l,mid,a,mid,c),k=query(p*2+1,mid+1,r,mid+1,b,c);if (f[j]<f[k]) return j;else return k;}
}
void ins(int l,int r){int j,k;j=query(1,1,n,l,r,l%2);k=query(1,1,n,j+1,r,r%2);zlt.l=l;zlt.r=r;zlt.u=j;zlt.v=k;heap.push(zlt);
}
int main(){scanf("%d",&n);f[0]=inf;fo(i,1,n) scanf("%d",&f[i]);build(1,1,n);ins(1,n);while (!heap.empty()){zlt=heap.top();heap.pop();l=zlt.l;r=zlt.r;j=zlt.u;k=zlt.v;ans[++tot]=f[j];ans[++tot]=f[k];if (j!=l) ins(l,j-1);if (j+1!=k) ins(j+1,k-1);if (k!=r) ins(k+1,r);}fo(i,1,n) printf("%d ",ans[i]);
}