题解：P11664 [JOI 2025 Final] 缆车 / Mi Teleférico

· · 题解

P11664 [JOI 2025 Final] 缆车

前言

vector 还是太好用了，二分跳了一晚上。

正文

这里定义 [l,r] 为好的区间即从 1 号点只经过编号 \in[l,r] 的公司修建的边，可以到达其他任意一个节点。

该图为一个 DAG，若要满足从 1 号点可以到达所有点，就要满足除 1 号点外所有点都有至少一条边通向它。因此问题就转化为了每个点所有通向它的权值是否有至少一个在 [l,r] 中。

设 r_i 为满足 [i,r_i] 为好区间的最小值。那该如何求 r_i？

发现该问题具有单调性，若 L\le l\le r\le R 且 [l,r] 是好区间，则 [L,R] 也是好区间。

因此，r_i\le r_j(i<j)。

证明：因为 i<j\le r_j=r_j，那 [i,r_j] 也一定是好区间因此 r_i\le r_j。

用双指针+线段树求即可。

回到题目，思考 X=0 时如何求解，即 r_L\le R 时为 Yes，否则为 No。

当 X\ne 0 时，可以得出区间长度越大则越优。询问可以转化为是否存在 i 满足 r_{L-X+i}\le R+i(0\le i\le X)，继续转化：

r_{L-X+i}\le R+i\\ R+i-r_{L-X+i}\ge 0\\ R-(L-X)+L-X+i-r_{L-X+i}\ge 0\\ f_i=i-r_i\\ R-L+X+f_{L-X+i}\ge 0\\

发现前面是定值，后面的一定越大越好，那就可以用 RMQ 求 [L-X,L] 中最大的 f_i。

因为原题的数据较大，要离散化，在两个点间的 r_i 是不变的，那 i 越大 f_i=i-r_i 就越大，特殊处理 f_R 就可以了。

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n , m , p , q;
const int N = 4e5 + 5 , inf = 0x7f7f7f7f7f7f7f7f;
vector <int> a[N] , g[N];
int d[4 * N] , R[N] , f[N][21] , lg[N] , s[N] , cc = 0;
void update (int l , int c , int s , int t , int p)
{
    if (s == t)
    {
        d[p] = c;
        return;
    }
    int m = s + t >> 1;
    if (l <= m) update (l , c , s , m , p << 1);
    if (l > m) update (l , c , m + 1 , t , p << 1 | 1);
    d[p] = min (d[p << 1] , d[p << 1 | 1]);
}
int getmax (int l , int r)
{
    int fl = lower_bound (s , s + cc , l) - s + 1 , fr = lower_bound (s , s + cc , r) - s + 1;
    if (fl == fr)
        return r - R[fr - 1];
    int Lg = lg[fr - fl];
    return max (max (f[fl][Lg] , f[fr - (1 << Lg)][Lg]) , r - R[fr - 1]);
}
signed main ()
{
    ios::sync_with_stdio (0) , cin.tie (0) , cout.tie (0);
    cin >> n >> m >> p;
    for (int i = 1;i <= m;i ++)
    {
        int v , w;
        cin >> v >> v >> w;
        g[v].push_back (w);
        s[cc ++] = w;
    }
    sort (s , s + cc) , cc = unique (s , s + cc) - s;
    for (int i = 1;i <= n;i ++)
        for (int j : g[i])
            a[lower_bound (s , s + cc , j) - s].push_back (i);
    int l = 0 , p = cc;
    memset (R , 0x7f , sizeof R);
    memset (d , -1 , sizeof d);
    update (1 , inf , 1 , n , 1);
    for (int r = 0;r < p;r ++)
    {
        for (int i : a[r])
            update (i , r , 1 , n , 1);
        while (l <= d[1]) R[l ++] = s[r];
    }
    s[p] = inf;
    lg[0] = -1;
    for (int i = 0;i < p;i ++) f[i + 1][0] = s[i] - R[i] , lg[i + 1] = lg[i + 1 >> 1] + 1;
    for (int k = 1;k <= lg[p];k ++)
        for (int i = 1;i + (1 << k) - 1 <= p;i ++)
            f[i][k] = max (f[i][k - 1] , f[i + (1 << k - 1)][k - 1]);
    cin >> q;
    for (int i = 1;i <= q;i ++)
    {
        int x , y , c;
        cin >> x >> y >> c;
        cout << (y - x + c + getmax (x - c , x) >= 0 ? "Yes\n" : "No\n");
    }
    return 0;
}