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

发表于 分类于 本文字数： 2.6k 阅读时长 ≈ 3 分钟

思路

注意到，DAG 符合条件当且仅当节点 的入度都不为零。

对于一个左端点 ，合法的 具有单调性。设最小的使 合法的 为 ，则区间 当 时合法。

现在多加了一个 的限制，可以移动 到 。
当 单增时 不降，故有 。
固定后 越大越好，故有 。
确定时只需要判断 是否符合条件即可。

问题变成对于 判断是否存在 满足 。由于 长度一定，则变为判断是否存在 ，维护区间最小值即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
const int N = 3e5+10,M = 4e5+10,INF = 0x3f3f3f3f;
int n,m,C,T;
int b[N+M*2],idx,R[N+M*2];
struct Query{
	int l,r,k;
}q[M];
struct Ed{
	int u,v,c;
}edge[N];
vector <int> ed[N+M*2];
int tr[N*4+M*8];
inline void build(int p,int nl,int nr){
	if(nl==nr){
		tr[p] = b[R[nl]];
		return ;
	}
	int mid = (nl+nr) >> 1;
	build(p<<1,nl,mid);
	build(p<<1|1,mid+1,nr);
	tr[p] = Min(tr[p<<1],tr[p<<1|1]);
}
inline void update(int p,int nl,int nr,int x,int k){
	if(nl==nr){
		tr[p] += k;
		return ;
	}
	int mid = (nl+nr) >> 1;
	if(x<=mid) update(p<<1,nl,mid,x,k);
	else update(p<<1|1,mid+1,nr,x,k);
	tr[p] = Min(tr[p<<1],tr[p<<1|1]);
}
inline int query(int p,int nl,int nr,int ql,int qr){
	if(ql>qr) return INF+INF;
	if(ql<=nl && nr<=qr) return tr[p];
	int mid = (nl+nr) >> 1;
	int res = INF+INF;
	if(ql<=mid) res = Min(res,query(p<<1,nl,mid,ql,qr));
	if(qr>mid) res = Min(res,query(p<<1|1,mid+1,nr,ql,qr));
	return res;
}
int main(){
	// freopen("in.in","r",stdin); 
	// freopen("out.out","w",stdout);
	
	read(n,m,C);
	for(int i=1,u,v,c;i<=m;++i){
		read(u,v,c);
		edge[i] = {u,v,c};
		b[++idx] = c;
	}
	read(T);
	for(int i=1,l,r,k;i<=T;++i){
		read(l,r,k);
		q[i] = {l,r,k};
		b[++idx] = l;
		b[++idx] = Max(1,l-k);
	}
	sort(b+1,b+1+idx);
	idx = unique(b+1,b+1+idx)-(b+1);
	b[idx+1] = INF+INF;
	for(int i=1;i<=m;++i){
		edge[i].c = lower_bound(b+1,b+1+idx,edge[i].c)-b;
		ed[edge[i].c].push_back(edge[i].v);
	}
	for(int i=1,now = 0;i<=idx;++i){
		while(query(1,1,n,2,n)<=0 && now+1<=idx+1){
			++now;
			for(int j=(int)ed[now].size()-1;j>=0;--j){
				update(1,1,n,ed[now][j],1);
			}
		}
		R[i] = now;
		for(int j=(int)ed[i].size()-1;j>=0;--j){
			update(1,1,n,ed[i][j],-1);
		}
	}
	build(1,1,idx);
	for(int i=1,l,r;i<=T;++i){
		l = lower_bound(b+1,b+1+idx,Max(1,q[i].l-q[i].k))-b;
		r = lower_bound(b+1,b+1+idx,q[i].l)-b;
		(query(1,1,idx,l,r)<=q[i].r-q[i].l+q[i].k) ? puts("Yes") : puts("No");
	}

	// fclose(stdin);
	// fclose(stdout);
	return 0;
}