题解：P13508 [OOI 2024] Burenka and Pether
Netheris
·
·
题解
好妙的题啊。
首先一个显然的性质：对于每个点 i，都能求出一个区间 (i,g_i]，使得 j\in(i,g_i]\wedge a_j>a_i 是 i 能通过一次转账到达 j 的充要条件。
接着考虑最小化转账次数。
不难发现，设当前点是 $x$，要到达 $y$，那么 $x$ 一定会走到 $(x,g_x]$ 中权值小于等于 $a_y$ 最大的点上。证明也很简单，考虑反证：设最大值的位置是 $u$，最优的选点在 $v$，那么当 $v<u$ 时，$g_v\le g_u$；当 $v>u$ 时，$u$ 可以不费代价走到 $v$。
这样我们按这个策略暴力去跳，就可以通过 sub6 和 sub7。
接着考虑优化跳的过程，麻烦的是每次选的最大值都要限制在 $[1,a_y]$。
如果能够扔掉这个最大值的范围限制，这道题就会好做不少。
不妨用值域分块：将值域分为 $\frac{n}{B}$ 块，对于一块 $[l,r]$，我们处理所有的 $a_y\in[l,r]$ 的询问。
显然，我们从 $x$ 开始跳，可以预处理后 $O(1)$ 跳到最后一个满足 $a_u\in[1,l)$ 且 $u$ 是最优的选点。接着考虑权值大于等于 $l$ 的，发现直接暴力跳，总量是 $O(n\sqrt n)$ 的。
然后就做完了。时间复杂度 $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;
}
```