【递归】【线段树】【堆】AtCoder Regular Contest 080 E

给你一个1~n的排列p，n是偶数，每次从中任选一对相邻的数出来，插到排列q的开头，如此循环，问你所能得到的字典序最小的排列q。

我们先确定q开头的两个数q1，q2，q1一定是p的奇数位的最小的数，而q2一定是q1后面最小的偶数位的数，这很显然。

然后记q1，q2在p中的位置分别是L，R，把p分成三段[1,L],[L+1,R-1],[R+1,n]，递归处理，当前区间[l,r]，每次取的一对的左端点L必然是与当前区间左端点l奇偶性相同的最小的数，而R必然是L右侧与当前区间左端点l奇偶性不同的最小的数。

可以对奇数位和偶数位分别维护一个线段树。

重点是输出答案，我们从前往后构造q，我们发现，所有的数对形成了一个树形结构，比如说[l,r]，通过之前我们说的过程，取得数对L,R，则[L,R]之间的数对都必须在L,R输出之后才能输出，我们把这些数对记作[L,R]的子树，递归把树建出来。

然后对我们构造出的这棵树，一开始把所有根的儿子加入堆，我们每次取当前堆里数对左侧的数最小的，输出，然后把它的儿子都加进堆，因为它的所有儿子都“解除了封锁”。如此直到堆空即可。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

priority_queue<int,vector<int>,greater<int> >Heap;

#define lson rt<<1,l,m

#define rson rt<<1|1,m+1,r

int v[200005],first[200005],nex[200005],e;

void AddEdge(int U,int V){

	v[++e]=V;

	nex[e]=first[U];

	first[U]=e;

}

int a[200005],cnt,ma[200005],pai[200005];

int minv[2][100005<<4],n,pos[200005];

void update(int o,int p,int v,int rt,int l,int r)

{

    if(l==r)

      {

        minv[o][rt]+=v;

        return;

      }

    int m=(l+r>>1);

    if(p<=m) update(o,p,v,lson);

    else update(o,p,v,rson);

    minv[o][rt]=min(minv[o][rt<<1],minv[o][rt<<1|1]);

}

int query(int o,int ql,int qr,int rt,int l,int r)

{

    if(ql<=l&&r<=qr) return minv[o][rt];

    int m=(l+r>>1);

    int res=2147483647;

    if(ql<=m) res=min(res,query(o,ql,qr,lson));

    if(m<qr) res=min(res,query(o,ql,qr,rson));

    return res;

}

void work(int l,int r,int f){

	if(l>=r){

		return;

	}

	int L=pos[query(l&1,ma[l],(l%2 == r%2) ? ma[r] : ma[r-1],1,1,n/2)];

	int R=pos[query((L+1)&1,ma[L+1],((L+1)%2 == r%2) ? ma[r] : ma[r-1],1,1,n/2)];

	pai[a[L]]=a[R];

	AddEdge(a[f],a[L]);

	work(l,L-1,f);

	work(L+1,R-1,L);

	work(R+1,r,f);

}

int main(){

//	freopen("c.in","r",stdin);

	scanf("%d",&n);

	for(int i=1;i<=n;++i){

		scanf("%d",&a[i]);

		pos[a[i]]=i;

		update(i&1,i/2+(i&1),a[i],1,1,n/2);

		ma[i]=i/2+(i&1);

	}

	if(n==2){

		printf("%d %d\n",a[1],a[2]);

		return 0;

	}

	work(1,n,0);

	for(int i=first[0];i;i=nex[i]){

		Heap.push(v[i]);

	}

	while(!Heap.empty()){

		int U=Heap.top(); Heap.pop();

		cnt+=2;

		printf("%d %d%c",U,pai[U],cnt==n ? '\n' : ' ');

		for(int i=first[U];i;i=nex[i]){

			Heap.push(v[i]);

		}

	}

	return 0;

}

巴特西

【递归】【线段树】【堆】AtCoder Regular Contest 080 E - Young Maids

最新文章

热门文章