专栏文章

题解：P13508 [OOI 2024] Burenka and Pether

NNetheris10+7
P13508题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minceag3
此快照首次捕获于
2025/12/02 00:07
3 个月前
此快照最后确认于
2025/12/02 00:07
3 个月前
查看原文
好妙的题啊。
首先一个显然的性质：对于每个点 ii，都能求出一个区间 (i,gi](i,g_i]，使得 j∈(i,gi]∧aj>aij\in(i,g_i]\wedge a_j>a_i 是 ii 能通过一次转账到达 jj 的充要条件。
gig_i 也不难求，考虑按权值从小到大扫描线，对于一个新加进来的点 ii，分别找左边和右边第一个小于 aia_i 的数，判一下是否满足编号差小于等于 dd，然后并查集缩一下就好了。
接着考虑最小化转账次数。
不难发现，设当前点是 xx，要到达 yy，那么 xx 一定会走到 (x,gx](x,g_x] 中权值小于等于 aya_y 最大的点上。证明也很简单，考虑反证：设最大值的位置是 uu，最优的选点在 vv，那么当 v<uv<u 时，gv≤gug_v\le g_u；当 v>uv>u 时，uu 可以不费代价走到 vv。
这样我们按这个策略暴力去跳，就可以通过 sub6 和 sub7。
接着考虑优化跳的过程，麻烦的是每次选的最大值都要限制在 [1,ay][1,a_y]。
如果能够扔掉这个最大值的范围限制，这道题就会好做不少。
不妨用值域分块：将值域分为 nB\frac{n}{B} 块，对于一块 [l,r][l,r]，我们处理所有的 ay∈[l,r]a_y\in[l,r] 的询问。
显然，我们从 xx 开始跳，可以预处理后 O(1)O(1) 跳到最后一个满足 au∈[1,l)a_u\in[1,l) 且 uu 是最优的选点。接着考虑权值大于等于 ll 的，发现直接暴力跳，总量是 O(nn)O(n\sqrt n) 的。
然后就做完了。时间复杂度 O(nn)O(n\sqrt n)。
CPP
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;bool f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int Maxn=3e5+5,B=1000;
int n,d,g123456789,q;
int a[Maxn],id[Maxn];
int g[Maxn];// 1 step, i -->  [i+1,g(i)]
struct bxj{
	int fa[Maxn];
	inline void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}
	int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
	inline void merge(int u,int v){fa[find(u)]=find(v);}
}F;
struct Query{int u,id;};
vector<Query>Q[Maxn];
int ans[Maxn];
int fa[Maxn],dep[Maxn],to[Maxn];
int las[Maxn],mx[B+5][B+5];
int b[Maxn],tot,h[Maxn];
inline void solve(int l,int r){
	tot=0;
	for(int i=1;i<=n;i++){
		if(l<=a[i]&&a[i]<=r)b[++tot]=i;
		h[i]=tot;
	}
	for(int i=1;i<=tot;i++)for(int j=i;j<=tot;j++)mx[i][j]=max(mx[i][j-1],a[b[j]]);
	for(int i=n;i;i--)if(a[i]<=r){
		int p=a[i];
		fa[p]=max(las[p],mx[h[i]+1][h[g[i]]]);
		if(fa[p]<p)fa[p]=0,to[p]=p,dep[p]=0;
		if(fa[p]&&fa[p]<l)dep[p]=dep[fa[p]]+1,to[p]=to[fa[p]];
		if(fa[p]>=l)dep[p]=0,to[p]=p;
	}
	for(int v=l;v<=r;v++){
		for(Query it:Q[v]){
			int x=a[it.u],res=0,p=1;
			while(x<v){
				res+=dep[x];x=to[x];
				int mx=las[x];
				while(p<=tot&&b[p]<=g[id[x]]){
					if(b[p]>id[x]&&a[b[p]]<=v)mx=max(mx,a[b[p]]);p++;
				}if(!mx){res=0;break;}
				x=mx;res++;
			}if(~ans[it.id])ans[it.id]=res;else ans[it.id]=(res>0);
		}
	}
	for(int i=1;i<=n;i++)las[i]=fa[i];
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read();d=read();g123456789=read();
	for(int i=1;i<=n;i++)a[i]=read(),id[a[i]]=i;
	set<int>s;s.insert(-2*n);s.insert(n*2);
	F.init(n);
	for(int i=1;i<=n;i++){
		int suf=(*s.lower_bound(id[i])),pre=(*prev(s.lower_bound(id[i])));
		if(pre+d>=id[i]&&F.find(pre)<id[i])F.merge(pre,id[i]);
		if(id[i]+d>=suf)F.merge(id[i],suf);
		g[id[i]]=min(n,F.find(id[i])+d);
		s.insert(id[i]);
	}
	q=read();
	for(int i=1;i<=q;i++){
		int op=read(),u=read(),v=read();
		if(op==1)ans[i]=-1;
		Q[a[v]].push_back({u,i});
	}
	for(int i=0;i*B<=n;i++)solve(max(1,i*B),min(n,i*B+B-1));
	for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
	return 0;
}

评论

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

正在加载评论...