专栏文章

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

llovely_nst
P11664题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqby23b
此快照首次捕获于
2025/12/04 02:17
3 个月前
此快照最后确认于
2025/12/04 02:17
3 个月前
查看原文

P11664 [JOI 2025 Final] 缆车

前言

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

正文

这里定义 [l,r][l,r] 为好的区间即从 11 号点只经过编号 ∈[l,r]\in[l,r] 的公司修建的边，可以到达其他任意一个节点。
该图为一个 DAG，若要满足从 11 号点可以到达所有点，就要满足除 11 号点外所有点都有至少一条边通向它。因此问题就转化为了每个点所有通向它的权值是否有至少一个在 [l,r][l,r] 中。
设 rir_i 为满足 [i,ri][i,r_i] 为好区间的最小值。那该如何求 rir_i？
发现该问题具有单调性，若 L≤l≤r≤RL\le l\le r\le R 且 [l,r][l,r] 是好区间，则 [L,R][L,R] 也是好区间。
因此，ri≤rj(i<j)r_i\le r_j(i<j)。
证明：因为 i<j≤rj=rji<j\le r_j=r_j，那 [i,rj][i,r_j] 也一定是好区间因此 ri≤rjr_i\le r_j。
用双指针+线段树求即可。
回到题目，思考 X=0X=0 时如何求解，即 rL≤Rr_L\le R 时为 Yes，否则为 No。
当 X≠0X\ne 0 时，可以得出区间长度越大则越优。询问可以转化为是否存在 ii 满足 rL−X+i≤R+i(0≤i≤X)r_{L-X+i}\le R+i(0\le i\le X)，继续转化：
rL−X+i≤R+iR+i−rL−X+i≥0R−(L−X)+L−X+i−rL−X+i≥0fi=i−riR−L+X+fL−X+i≥0r_{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][L-X,L] 中最大的 fif_i。
因为原题的数据较大，要离散化，在两个点间的 rir_i 是不变的，那 ii 越大 fi=i−rif_i=i-r_i 就越大，特殊处理 fRf_R 就可以了。

AC Code

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

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...