CF1662F
遇到绝对值想想拆开。
考虑优化 bfs 时扩展过程,设当前点为 i,考虑 i,j 连边。
|\(i-j\)|\(\leq\) \(\min(p_i,p_j)\),则 j 至少应该在 [\(i-p_i\),\(i+p_i\)]。
分类讨论一下
\(j\geq i\) 时 \(j-i\leq p_j\),则 \(i\geq j-p_j\)
\(j\leq i\) 时 \(i-j\leq p_j\),则 \(i\leq j+p_j\)
于是线段树维护区间最小值和最大值,因为 bfs,每个点只被取一次,时间复杂度 \(\Omicron(n\log n)\)。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<bitset>
using namespace std;
#define db double
#define ll long long
#define ull unsigned long long
#define ld long double
#define b1t bitset
#define ls p<<1
#define rs p<<1|1
const int MAXN=2e5+5;
const int INF=0x3f3f3f3f;
const int Mod=1e9+7;
void read(int &x){
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){
if(s=='-') f=-1;s=getchar();
}
while(s>='0'&&s<='9'){
x=(x<<3)+(x<<1)+(s^48);s=getchar();
}
x*=f;
}
ll ksm(ll a,int b){
ll res=1;
while(b){
if(b&1) res=res*a%Mod;a=a*a%Mod;b>>=1;
}return res;
}
int T,n,ss,tt,va[MAXN],dp[MAXN];
struct tree{
int l,r,ma,mi;
}t[MAXN<<2];
queue<int> q;
void pup(int p){
t[p].ma=max(t[ls].ma,t[rs].ma);
t[p].mi=min(t[ls].mi,t[rs].mi);
}
void bui(int p,int l,int r){
t[p].l=l;t[p].r=r;
if(l==r){
t[p].mi=l-va[l];t[p].ma=l+va[l];
if(l==ss) t[p].mi=INF,t[p].ma=-INF;
return;
}
int mid=(l+r)>>1;
bui(ls,l,mid);bui(rs,mid+1,r);
pup(p);
}
void que1(int p,int l,int r,int x){
if(t[p].mi>x) return;
if(r<1||l>n) return;
if(t[p].r<l||t[p].l>r) return;
if(t[p].l==t[p].r){
t[p].mi=INF;t[p].ma=-INF;dp[t[p].l]=dp[x]+1;q.push(t[p].l);return;
}
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) que1(ls,l,r,x);
if(r>mid) que1(rs,l,r,x);
pup(p);
}
void que2(int p,int l,int r,int x){
if(t[p].ma<x) return;
if(r<1||l>n) return;
if(t[p].r<l||t[p].l>r) return;
if(t[p].l==t[p].r){
t[p].ma=-INF;t[p].mi=INF;dp[t[p].l]=dp[x]+1;q.push(t[p].l);return;
}
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) que2(ls,l,r,x);
if(r>mid) que2(rs,l,r,x);
pup(p);
}
int main(){
read(T);
while(T--){
read(n);read(ss);read(tt);
for(int i=1;i<=n;i++) dp[i]=0,read(va[i]);
q.push(ss);
bui(1,1,n);
while(q.size()){
int now=q.front();q.pop();
que1(1,now+1,min(n,now+va[now]),now);
que2(1,max(1,now-va[now]),now-1,now);
}
printf("%d\n",dp[tt]);
}
return 0;
}