返回首页

【ONTAK2015】Tasowanie 题解

BZOJ权限题

题解

·首先来解释一下“二路归并”

·就是有两个队列，每次可以选取一个队列，取出它的队头元素加入一个新的队列，同时将其在原队列中弹出

·那么我们使用后缀数组来秒掉这题

·将两个序列拼接到一起，中间插一个正无穷，后面再插一个正无穷

·然后求出后缀数组，再搞出Rank，就可以直接比较哪个决策更优了

·两个指针，分别指向拼接后两个序列的开头位置，利用Rank数组比较决策的优秀性，以此决定哪个指针右移

#include<bits/stdc++.h>
using namespace std;

const int N=400010;
int s[N];
int sa[N],Rank[N];
int x[N],y[N],c[N],tmp[N];

void get_sa(int n,int m)
{
	for(int i=1;i<=n;i++) c[x[i]=s[i]]++;
	for(int i=1;i<m;i++) c[i+1]+=c[i];
	for(int i=n;i>=1;i--) sa[c[x[i]]--]=i;
	for(int k=1;k<=n;k<<=1)
	{
		int num=0;
		for(int i=n-k+1;i<=n;i++) y[++num]=i;
		for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
		for(int i=1;i<=m;i++) c[i]=0;
		for(int i=1;i<=n;i++) tmp[i]=x[y[i]];
		for(int i=1;i<=n;i++) c[tmp[i]]++;
		for(int i=1;i<m;i++) c[i+1]+=c[i];
		for(int i=n;i>=1;i--) sa[c[tmp[i]]--]=y[i];
		swap(x,y);x[sa[1]]=1;num=1;
		for(int i=2;i<=n;i++)
			x[sa[i]]=(y[sa[i]]!=y[sa[i-1]]||y[sa[i]+k]!=y[sa[i-1]+k])?++num:num;
		if(num==n) break;
		m=num;
	}
	for(int i=1;i<=n;i++) Rank[sa[i]]=i;
}


int main()
{
	int l1,l2;
	scanf("%d",&l1);
	for(int i=1;i<=l1;i++) scanf("%d",s+i);
	s[l1+1]=1001;
	scanf("%d",&l2);
	s[l1+l2+2]=1001;
	for(int i=1;i<=l2;i++) scanf("%d",s+l1+1+i);
	get_sa(l1+l2+2,1001);
	int p1=1,p2=l1+2;
	while(p1<=l1||p2<=l1+l2+1)
		if((p1<=l1&&Rank[p1]<Rank[p2])||p2>l1+l2+1) printf("%d ",s[p1++]);
		else printf("%d ",s[p2++]);
	return 0;
}