专栏文章

NOIP2024 T4 题解

AAFewSunsqwq
题解参与者 4已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miqxxo7n
此快照首次捕获于
2025/12/04 12:33
3 个月前
此快照最后确认于
2025/12/04 12:33
3 个月前
查看原文

题目大意

nn 个点的树，qq 此询问 l,r,kl,r,k，求 max⁡l≤l′≤r′≤r,r′−l′+1≥kdeplca⁡{l′,l′+1,…,r′}\max\limits_{l\leq l' \leq r' \leq r,r'-l'+1 \geq k}{dep_{\operatorname{lca}\{l',l'+1,\dots,r'\}}}
n,q≤5×105n,q \leq 5\times 10^5

题目分析

首先一定有 r′−l′+1=kr'-l'+1=k，因为不劣。然后考虑真正有用的区间大概成一个树形结构，只有 O(n)\mathcal O(n) 个。这部分可以将相邻 lca⁡\operatorname{lca} 的深度插到堆里，每次取最大的合并？
然后只需要满足有用区间与询问区间的交 ≥k\geq k，求权值最大值。
对于有用区间在询问区间右边的情况，可以把权值放到有用区间的左端点，然后区间查询 [l,r−k+1][l,r-k+1] 的最大值。右边同理。内部再加个有用区间长度 ≥k\geq k 的限制。外部直接求全局答案。
二位偏序（长度 ≥k\geq k，然后单点修改区间查询）。复杂度单 log⁡\log。

代码

只能说退役 4 个月代码能力为 0，场上没时间写了。很遗憾没能 AK。
upd：
CPP
#include<bits/stdc++.h>
using namespace std;
using namespace my_std;
ll n,q,m=0,head[500050],cnt=0,dep[500050],f[500050][19];
ll val[500050],st[500050],top=0,lc[500050],rc[500050],L[500050],R[500050];
ll ST[19][500050],lg[500050],ans[500050];
struct edge{
	ll nxt,to;
}e[1000010];
struct node{
	ll l,r,k,v,id;
}p[500050],a[1000010];
struct seg{
	#define LC x<<1
	#define RC x<<1|1
	ll tree[2000020];
	il void pushup(ll x){
		tree[x]=max(tree[LC],tree[RC]);
	}
	void mdf(ll x,ll l,ll r,ll pos,ll v){
		if(l==r){
			tree[x]=max(tree[x],v);
			return;
		}
		ll mid=(l+r)>>1;
		if(pos<=mid) mdf(LC,l,mid,pos,v);
		else mdf(RC,mid+1,r,pos,v);
		pushup(x);
	}
	ll query(ll x,ll l,ll r,ll ql,ll qr){
		if(ql<=l&&r<=qr) return tree[x];
		ll mid=(l+r)>>1,res=0;
		if(ql<=mid) res=max(res,query(LC,l,mid,ql,qr));
		if(mid<qr) res=max(res,query(RC,mid+1,r,ql,qr));
		return res;
	}
}Tl,Tr;
il bl operator<(const node &x,const node &y){
	return x.k>y.k;
}
il void add(ll u,ll v){
	e[++cnt].nxt=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
void dfs(ll fa,ll u){
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	fr(i,1,18) f[u][i]=f[f[u][i-1]][i-1];
	go(u){
		ll v=e[i].to;
		if(v==fa) continue;
		dfs(u,v);
	}
}
il ll get_lca(ll x,ll y){
	if(dep[x]<dep[y]) swap(x,y);
	pfr(i,18,0) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	pfr(i,18,0){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
void dfs2(ll x){
	L[x]=x-1;
	R[x]=x;
	if(lc[x]){
		dfs2(lc[x]);
		L[x]=L[lc[x]];
	}
	if(rc[x]){
		dfs2(rc[x]);
		R[x]=R[rc[x]];
	}
}
il ll querymin(ll l,ll r){
	ll tmp=lg[r-l+1];
	return min(ST[tmp][l],ST[tmp][r-(1ll<<tmp)+1]);
}
int main(){
	n=read();
	fr(i,2,n){
		ll u=read(),v=read();
		add(u,v);
		add(v,u);
	}
	dfs(0,1);
	fr(i,2,n) val[i]=get_lca(i-1,i);
	fr(i,2,n){
		ll tmp=top;
		while(tmp&&dep[val[i]]<dep[val[st[tmp]]]) tmp--;
		if(tmp) rc[st[tmp]]=i;
		if(tmp<top) lc[i]=st[tmp+1];
		top=tmp;
		st[++top]=i;
	}
	dfs2(st[1]);
	fr(i,1,n) a[++m]=(node){i,i,1,dep[i],0};
	fr(i,2,n) a[++m]=(node){L[i],R[i],R[i]-L[i]+1,dep[val[i]],0};
	fr(i,2,n) lg[i]=lg[i>>1]+1;
	fr(i,2,n) ST[0][i]=dep[val[i]];
	fr(j,1,18) fr(i,2,n-(1ll<<j)+1) ST[j][i]=min(ST[j-1][i],ST[j-1][i+(1ll<<(j-1))]);
	q=read();
	fr(i,1,q){
		p[i].l=read();
		p[i].r=read();
		p[i].k=read();
		p[i].id=i;
		if(p[i].l==p[i].r) p[i].v=dep[p[i].l];
		else p[i].v=querymin(p[i].l+1,p[i].r);
	}
	sort(p+1,p+q+1);
	sort(a+1,a+m+1);
	ll pos=1;
	fr(i,1,q){
		while(pos<=m&&a[pos].k>=p[i].k){
			Tl.mdf(1,1,n,a[pos].l,a[pos].v);
			Tr.mdf(1,1,n,a[pos].r,a[pos].v);
			pos++;
		}
		p[i].v=max(p[i].v,max(Tl.query(1,1,n,p[i].l,p[i].r-p[i].k+1),Tr.query(1,1,n,p[i].l+p[i].k-1,p[i].r)));
	}
	fr(i,1,q) ans[p[i].id]=p[i].v;
	fr(i,1,q) writeln(ans[i]);
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...