「51nod 1863」Travel

发表于

Fancy 年青的时候喜欢旅行。据他回忆说，那曾是一段有始有终的旅行。

他来到了一个叫 Fancy 的理想国。那里有许许多多的 FancyCat 。最开始的时候，同一种 FancyCat 会形成一个部落，拥有特定的一块领地。Fancy 第一次来这里的时候还 Too Young ，现在他将故地重游。但由于多年的演变，部落分分合合，现在两个不一样的部落有可能也是由同一种 FancyCat 组成。

Fancy 开始了他的徒步路程。每次他经过某一个部落，他将收到由该部落种类的纪念品一份。Fancy 很喜欢收集纪念品。他是一个性情中人，越喜欢的纪念品他就越想得到，而且要越多越好。Fancy 列出了一张纪念品喜欢程度的排名表。在这个表中越靠前的纪念品表示 Fancy 越喜欢。

由于理想国过于庞大，虽然拥有地图，但 Fancy 也会因为找不到地图上对应的位置而经常迷路。 Fancy 觉得与其在地图中苦苦挣扎不如随机走。而且他坚信一定能走到终点！ Fancy 在旅行开始前，想到可以先计算一下期望得到的每个纪念品的数量，不过由于图中环的存在，给计算带来了很大困难。于是 Fancy 打算只计算一下自己完全随机乱走的情况下最坏能得到的那些纪念品。对于两条旅行线路的比较，他采取了如下的方法：找出在排名表中最靠前的一个纪念品，满足两条线路中获得的该纪念品数量不相等。这时候，该纪念品多的那一条线路更优。

你要做的工作就是计算出最坏情况下的得到纪念品序列。

Constraints

n≤100000n\leq 100000 ， m≤500000m\leq 500000

Solution

据题意，显然最坏情况就是从 11 到 nn 的最短路，这里的最短即为题意中的最劣，每个点的 disdis 可以按排名表统计为一个序列。

主要问题在两个序列的比较，这里我们使用主席树来维护序列的哈希值，比较两个序列的字典序时在主席树上二分即可。

详见代码，时间复杂度 O((n+m)lognlogn)O((n+m)lognlogn) 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<cstdio>
#include<algorithm> 
#include<cstring>
#include<queue>
#define LL long long
using namespace std;
const int N=1e5+5;
const LL base=20010311;
int n,m,cnt,idx,x,y,t,cur;
int first[N],id[N],rk[N],a[N];
int rt[N],ls[N*50],rs[N*50];
LL bit[N],v[N*50];
struct edge{int to,next;}e[N*10];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
void add(int &x,int l,int r,int c)
{
	int t=x;x=++idx;
	ls[x]=ls[t];rs[x]=rs[t];v[x]=v[t];
	if(l==r){v[x]++;return;}
	int mid=(l+r)>>1;
	if(c<=mid)add(ls[x],l,mid,c);
	else add(rs[x],mid+1,r,c);
	v[x]=v[ls[x]]*bit[r-mid]+v[rs[x]];
}
bool cmp(int x,int y)
{
	if(v[x]==v[y])return false;
	int l=1,r=n;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(v[ls[x]]!=v[ls[y]])x=ls[x],y=ls[y],r=mid;
		else x=rs[x],y=rs[y],l=mid+1;
	}
	return v[x]<v[y];
}
struct node
{
	int x,t;
	bool operator < (const node& a)const{return !cmp(t,a.t);} 
};
priority_queue<node> q;
void dfs(int x,int l,int r)
{
	if(!x)return;
	if(l==r){for(int i=1;i<=v[x];i++)printf("%d ",id[l]);return;}
	int mid=(l+r)>>1;
	dfs(ls[x],l,mid);dfs(rs[x],mid+1,r);
}
int main()
{
	n=read();m=read();bit[0]=1;
	for(int i=1;i<=n;i++)bit[i]=bit[i-1]*base;
	for(int i=1;i<=n;i++)
		id[i]=read(),rk[id[i]]=i;
	for(int i=1;i<=n;i++)
		a[i]=read(),a[i]=rk[a[i]];
	for(int i=1;i<=m;i++)
		x=read(),y=read(),ins(x,y),ins(y,x);
	q.push((node){1,rt[1]});
	while(!q.empty())
	{
		x=q.top().x;t=q.top().t;q.pop();
		if(t!=rt[x])continue;
		cur=rt[x];add(cur,1,n,a[x]);
		for(int i=first[x];i;i=e[i].next)
		{
			int to=e[i].to;
			if(!rt[to]||cmp(cur,rt[to]))
			{
				rt[to]=cur;
				q.push((node){to,rt[to]});
			}
		}
	}
	add(rt[n],1,n,a[n]);
	dfs(rt[n],1,n);
	return 0;
}