P11664 [JOI 2025 Final] 缆车 / Mi Telefrico

思路

注意到，DAG 符合条件当且仅当节点 \(2 \sim n\) 的入度都不为零。

对于一个左端点 \(l\)，合法的 \(r\) 具有单调性。设最小的使 \(l\) 合法的 \(r\) 为 \(R_l\)，则区间 \([q_l,q_r]\) 当 \(R_{q_l} \le q_r\) 时合法。

现在多加了一个 \(X\) 的限制，可以移动 \([q_l,q_r]\) 到 \([q_l',q_r']\)。
当 \(l\) 单增时 \(R_l\) 不降，故有 \(q_l' \le q_l\)。
\(q_l'\) 固定后 \(q_r'\) 越大越好，故有 \(q_r' = q_l'+q_r-q_l+X\)。
\([q_l',q_r']\) 确定时只需要判断 \(R{q_l'}\) 是否符合条件即可。

问题变成对于 \(q_l-X \le q_l' \le q_l\) 判断是否存在 \(q_l'\) 满足 \(R_{q_l'}\le q_r'\)。由于 \([q_l',q_r']\) 长度一定，则变为判断是否存在 \(R_{q_l'}-q_l' \le q_r-q_l+X\)，维护区间最小值即可。

代码

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