本文主要是介绍洛谷P7518 [省选联考 2021 A/B 卷] 宝石，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

P7518 [省选联考 2021 A/B 卷] 宝石

题目来源
乍一看没有任何思路，于是当年我打了一个模拟程序混了点分就跑路了……然后现在还是得看题解……还得努力啊
这里用主席树+倍增+二分，复杂度O(nlog² (n)),理解起来较为简单，但是对我来说太难想了。

一、题目初步转化

1.其实这道题也不是一点线索都没有，我们看到询问之间没有修改，要么离线要么大力预处理，然后就可以往倍增上想（联想倍增求LCA和ST表）。不过只有当某一个2^k 长度的区间可以由两个长度为2^k-1 的区间合并才能用倍增，这就对我们倍增数组的设计提出了要求（事实上，即便是我知道这道题可以用倍增做之后，我也还是一头雾水）。
2.然后不难想到将路径拆成两段以LCA为分界线的路径，关键就是题干要求我们必须奥找顺序收集，这给两段路径的拼接合并造成了麻烦。
3.还有一个问题就是，我们需要找到快速确定倍增起点的方法，也就是要知道如何快速地寻找一段路径上某一特定编号的最大深度。
我就想到这三个点就想不下去了，于是看了看题解……

二、正确思路

首先先将宝石的编号调整一下，使得我们按照1~c的顺序收集宝石。
1.先来看第一个问题，倍增数组的设计。令 f1[x][i] 表示祖先节点中离x最近的宝石编号为w[x]+2ⁱ 的点 ，f2[x][i] 表示 祖先节点中离x最近的宝石编号为w[x]-2ⁱ 的点 。于是只要初值预处理好就行了。（也没有多么多么难是不是）
2.我们可以看出预处理与第三个问题是一致的，而解决方法就是主席树，对每一个节点存储其到根节点的路径上的宝石信息。具体地，主席树从根节点开始更新，主席树中叶子节点维护某一宝石编号最近一次出现在哪一个点上，在从父节点到子节点的过程中最多只有一个节点的信息被修改了，于是可以应用主席树。至于询问，假设一段路径[l,r]中r=LCA(l,r),那么从 点l上的主席树 查到的点的深度如果不大于r，就说明这段区间有该种宝石。
感觉已经尽力了但是我还是感觉说不太明白qwq……
3.接下来就只剩第二个问题——如何合并。我们将路径(s,t)拆成(s,LCA)和(LCA，t)两段路径。(s,LCA)这段直接倍增跳就行了，关键就是(LCA,t)这段下行路径。我们预处理的倍增数组只能向上找不能向下找，怎么办？枚举向上爬的起点，然后判断能不能和左侧链接上。这时候我们发现，这个起点是可二分的！（至于为什么可二分，我想咕咕地说，这是显然成立的）然后就是二分答案倍增验证，复杂度为log² (n)级别。
于是由于n,q同阶，总复杂度O(nlog² (n))。

不愧是省选题……

三、代码

分析了这么长时间终于到代码环节了……

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
typedef long long LL;
il int read(){
	int s=0,w=1;char c=getchar();
	while(c<'0'||c>'9'){ if(c=='-') w=-1;c=getchar();}
	while(c>='0'&&c<='9'){ s=(s<<1)+(s<<3)+c-'0';c=getchar();}
	return s*w;
} 
const int N=2e5+10;
int n,m,c,T,a[N],to[N],rt[N],ed;
int f1[N][25],f2[N][25],f[N][25],dep[N];
namespace Graph{
	int head[N],ver[N<<1],nxt[N<<1],Gt;
	il void addedge(int u,int v){
		ver[++Gt]=v,nxt[Gt]=head[u],head[u]=Gt;
		ver[++Gt]=u,nxt[Gt]=head[v],head[v]=Gt;
	}
} using namespace Graph;
namespace ZXS{//ZHU XI SHU
	struct Seg{ int ch[2],id; }tree[N<<5];
	int ID;
	#define lc(x) tree[x].ch[0]
	#define rc(x) tree[x].ch[1]
	il void build(int &x,int l,int r){
		x=++ID,tree[x].id=0;
		if(l==r) return;
		int mid=l+r>>1;
		build(lc(x),l,mid),build(rc(x),mid+1,r);
	}
	il void upd(int &p,int q,int l,int r,int aim,int val){
		if(!p) p=++ID;
		if(l==r){ tree[p].id=val;return; }
		int mid=l+r>>1;
		if(aim<=mid) upd(lc(p),lc(q),l,mid,aim,val),rc(p)=rc(q);
		else lc(p)=lc(q),upd(rc(p),rc(q),mid+1,r,aim,val);
	}
	il int que(int x,int l,int r,int aim){
		if(l==r) return tree[x].id;
		int mid=l+r>>1;
		if(aim<=mid) return que(lc(x),l,mid,aim);
		return que(rc(x),mid+1,r,aim);
	}
	#undef lc
	#undef rc 
}
il void dfs1(int x,int F){
	ZXS::upd(rt[x],rt[F],1,c,a[x],x);
	if(a[x]<c) f1[x][0]=ZXS::que(rt[x],1,c,a[x]+1);
	if(a[x]>1) f2[x][0]=ZXS::que(rt[x],1,c,a[x]-1);
	dep[x]=dep[F]+1,f[x][0]=F;
	for(re int i=head[x],v;i;i=nxt[i]){
		v=ver[i];if(v==F) continue;
		dfs1(v,x);
	}
}
il int getlca(int x,int y){
	if(x==y) return x;
	if(dep[x]<dep[y]) swap(x,y);
	for(re int i=20;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(re int i=20;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
int main()
{
	n=read(),m=read(),c=read(),ed=20;
	//step1:input
	for(re int i=1;i<=c;i++) to[read()]=i;
	for(re int i=1;i<=n;i++){
		a[i]=read();
		if(!to[a[i]]) to[a[i]]=++c;
		a[i]=to[a[i]];
	}
	for(re int i=1,u,v;i<n;i++) u=read(),v=read(),addedge(u,v);
	//step2:prework
	ZXS::build(rt[0],1,c);
	dfs1(1,0);
	for(re int i=1;i<=ed;i++){
		for(re int j=1;j<=n;j++){
			f1[j][i]=f1[f1[j][i-1]][i-1];
			f2[j][i]=f2[f2[j][i-1]][i-1];
			f[j][i]=f[f[j][i-1]][i-1];
		}
	}
	//step3:work
	T=read();
	while(T--){
		int s=read(),t=read(),x=ZXS::que(rt[s],1,c,1),LCA=getlca(s,t),p=0;
		if(dep[x]>=dep[LCA]){
			p=1;
			for(re int i=ed;i>=0;i--){
				if(dep[f1[x][i]]>=dep[LCA]) x=f1[x][i],p+=1<<i;
			}
		}
		int l=p,r=c+1;
		while(r-l>1){
			int mid=l+r>>1,y=ZXS::que(rt[t],1,c,mid);
			bool flag=0;
			if(y && dep[y]>=dep[LCA]){
				for(re int i=ed;i>=0;i--){
					if(dep[f2[y][i]]>=dep[LCA]) y=f2[y][i];
				}
				flag=(a[y]<=p+1);
			}
			flag?l=mid:r=mid;
		}
		printf("%d\n",l);
	}
}
/*
9 3 3
1 2 3
2 1 2 2 1 2 2 3 2
1 2
2 3
2 4
1 5
5 7
7 8
1 6
6 9
3
9 8
3 4
7 8

3
2
0
*/

太久没写主席树和倍增了，出了一些个小问题，终究不是自己想出来的，就可能出现这种情况，还是要多练练的

这篇关于洛谷P7518 [省选联考 2021 A/B 卷] 宝石的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！