【AtCoder Regular Contest 080 E】Young Maids | Mrsrz's blog

贪心。

题目大意：

给定一个长度为偶数的排列。每次选择相邻两个数，按照原来的顺序加入到队列头部。

求最后可能形成的队列中，字典序最小的。

题解：

从后往前倒着考虑。

最后一次选择一定是选一个奇数位置和一个偶数位置（将考虑的段的第一个位置看成奇数位置，顺序不能调换）。

我们用数据结构维护偶数位置的最小值，以及奇数位置的最小值，然后贪心地选择最小的即可。

选择完以后，整个数列会被分成三个部分。接下来的选择不能跨区域进行。

我们要求每次的选择都是尽可能小，所以要选择一个能产生的位置最小的数。

用一个堆维护所有不同的段，以奇数位置的最小值为关键字排序。

每次取出堆顶元素进行考虑即可。

时间复杂度 $O(n\log n)$。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2e5+5;
int n,p[N],pos[N],b[N];
bool vis[N];
struct data{
    int l,r,x,y;
    inline bool operator<(const data&rhs)const{return x>rhs.x;}
};
priority_queue<data>q;
struct sgt_{
    int d[N<<2];
    void build(int l,int r,int o){
        if(l==r)d[o]=b[l];else{
            const int mid=l+r>>1;
            build(l,mid,o<<1),build(mid+1,r,o<<1|1);
            d[o]=min(d[o<<1],d[o<<1|1]);
        }
    }
    void modify(int l,int r,int o,const int&pos,const int&x){
        if(l==r)d[o]=x;else{
            const int mid=l+r>>1;
            if(pos<=mid)modify(l,mid,o<<1,pos,x);else modify(mid+1,r,o<<1|1,pos,x);
            d[o]=min(d[o<<1],d[o<<1|1]);
        }
    }
    int query(int l,int r,int o,const int&L,const int&R){
        if(L<=l&&r<=R)return d[o];
        const int mid=l+r>>1;
        if(L<=mid&&mid<R)return min(query(l,mid,o<<1,L,R),query(mid+1,r,o<<1|1,L,R));
        if(L<=mid)return query(l,mid,o<<1,L,R);
        return query(mid+1,r,o<<1|1,L,R);
    }
}t[2];
void add(int l,int r){
    if(l>r)return;
    int x=t[l&1].query(1,n,1,l,r),y=t[l&1^1].query(1,n,1,pos[x]+1,r);
    q.push((data){l,r,x,y});
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",p+i),pos[p[i]]=i;
    memset(b,0x3f,sizeof b);
    for(int i=1;i<=n;i+=2)b[i]=p[i];
    t[1].build(1,n,1);
    memset(b,0x3f,sizeof b);
    for(int i=2;i<=n;i+=2)b[i]=p[i];
    t[0].build(1,n,1);
    add(1,n);
    while(!q.empty()){
        data u=q.top();q.pop();
        printf("%d %d ",u.x,u.y);
        add(u.l,pos[u.x]-1),add(pos[u.x]+1,pos[u.y]-1),add(pos[u.y]+1,u.r);
    }
    return 0;
}