[P14610] [NWRRC 2025] Keys and Grates 题解

· · 题解

实际上只需要模拟整个流程即可。

先尝试 S\to T，可能会有阻碍，于是 S\to L_1，其中 \displaystyle L_1=\displaystyle\min_{b_i\isin[S,T]}a_i，拿到通过 S\to T 所有门的钥匙。然后尝试 S\to L_1，可能会有阻碍，于是 S\to R_1，其中 \displaystyle R_1=\max_{b_i\isin[L_1,S]}a_i，拿到通过 S\to L_1 所有门的钥匙，以此类推。终止条件是，没有门在 S\to x 路径上。

判定无解时，注意到 L 单增，R 单减，若不满足这两个条件中任意一个，则说明存在一个钥匙落在了无法到达的位置。当然 S\to x 时，如果有一个钥匙被其对应的门挡在了前面，也无解，具体可以前缀和找是否有 b_i\isin[S,x] 使得 b_i<a_i，或者是否有 b_i\isin[x,S] 使得 b_i>a_i。

离散化 a,b,S,T 后使用 ST 表即可快速查 \displaystyle\min_{b_i\isin[l,r]}a_i 与 \displaystyle\max_{b_i\isin[l,r]}a_i。时间复杂度 \mathcal{O}(n\log n)。

:::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef long long ll;
const ll maxn=500007,ee=1e18,V=1e7;
ll n,m,S,T,a[maxn],b[maxn],c[maxn],su[maxn][2];
ll mx[maxn][20],mn[maxn][20],ans;
void ups(ll &a,ll b){a=min(a,b);}
ll QMN(ll l,ll r){
    if(l>r) return ee;
    ll k=__lg(r-l+1);
    return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
ll QMX(ll l,ll r){
    if(l>r) return -ee;
    ll k=__lg(r-l+1);
    return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
ll solve(ll l,ll r,bool typ){
    if(l>r) return 0;
    if(typ==0){
        if(su[r][0]-su[S-1][0]) return -1;
        ll mn=QMN(S,r);
        if(l>=mn) return -1;
        if(mn>=S) return 0;
        ll res=solve(mn,r,1);
        if(res==-1) return -1;
        return res+2*(c[S]-c[mn]);
    }else{
        if(su[S][1]-su[l-1][1]) return -1;
        ll mx=QMX(l,S);
        if(r<=mx) return -1;
        if(mx<=S) return 0;
        ll res=solve(l,mx,0);
        if(res==-1) return -1;
        return res+2*(c[mx]-c[S]);
    }
}
ll solve(void){
    m=2*n+2;
    for(ll i=1;i<=n;i++) c[2*i-1]=a[i],c[2*i]=b[i];
    c[2*n+1]=S,c[2*n+2]=T;
    sort(c+1,c+1+m);
    for(ll i=1;i<=n;i++){
        a[i]=lower_bound(c+1,c+1+m,a[i])-c;
        b[i]=lower_bound(c+1,c+1+m,b[i])-c;
    }
    S=lower_bound(c+1,c+1+m,S)-c;
    T=lower_bound(c+1,c+1+m,T)-c;
    if(S>T){
        S=m-S+1,T=m-T+1;
        for(ll i=1;i<=n;i++) a[i]=m-a[i]+1,b[i]=m-b[i]+1;
        for(ll i=1;i<=m;i++) c[i]=V-c[i];
        reverse(c+1,c+1+m);
    }
    for(ll i=1;i<=m;i++){
        mn[i][0]=ee,mx[i][0]=-ee;
        su[i][0]=su[i][1]=0;
    }
    for(ll i=1;i<=n;i++){
        mn[b[i]][0]=mx[b[i]][0]=a[i];
        if(a[i]>b[i]) su[b[i]][0]++;
        else su[b[i]][1]++;
    }
    for(ll i=1;i<=m;i++) su[i][0]+=su[i-1][0],su[i][1]+=su[i-1][1];
    for(ll j=1;j<=19;j++){
        for(ll i=1;i+(1<<j)-1<=m;i++){
            mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
            mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
        }
    }
    ans=solve(0,T,0);
    if(ans==-1) return -1;
    return ans+c[T]-c[S];
}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    ll Tc=1; cin>>Tc;
    for(;Tc--;){
        cin>>n>>S>>T;
        for(ll i=1;i<=n;i++) cin>>a[i]>>b[i];
        cout<<solve()<<"\n";
    }
    return 0;
}

:::