自动搬运

查看原文

来自洛谷，原作者为

	lovely_nst 666这个入是桂

搬运于2025-08-24 23:09:16，当前版本为作者最后更新于2025-02-06 08:15:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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;
}