CF685E 题解

吐槽一下，为啥这道题 \(\mathcal{O}(nm)\) 可以过。联考的时候做到了这道题，还一直在想更快的算法。。。

然后，这联考的数据是自己出的，有 \(s=t\) 的情况，我反正是完全没有想到，又因为是捆绑测试，直接痛失 \(100pts\)。

首先考虑转化一下题目。对于一个询问 \(l,r,s,t\)，就相当于是让你从第 \(l\) 到 \(r\) 条边中选出一些边，使得依次按这些边走可以从 \(s\) 到 \(t\)。

先考虑只有这一个询问的情况。我们可以令数组 \(a_{i,j}\) 表示 \(i\) 能否到达 \(j\)，然后按顺序枚举第 \(l\) 到 \(r\) 条边。设现在这条边是 \(u,v\)，考虑应该更新哪些值。可以发现如果有一个点 \(x\) 能到达 \(u\)，那么将 \(u,v\) 这条边加进来之后 \(x\) 就也能到达 \(v\) 了。所以如果 \(a_{x,u}=1\) 或 \(a_{x,v}=1\)，那么就应该更新 \(a_{x,v}=1\) 或 \(a_{x,u}=1\)，简化一下就是对于所有 \(1\le x\le n\)，\(a_{x,u} = a_{x,v} = a_{x,u}|a_{x,v}\)。

现在是多组询问，我们可以将询问按 \(r\) 排一遍序，然后还是依次枚举每一条边，每次更新所有 \(r\) 为当前边的询问。

但是每个询问还有 \(l\) 的限制，所以 \(a\) 数组就不能只单纯地记 \(0\) 和 \(1\) 了，而应该记一个数 \(x\)。\(a_{i,j}=x\) 就表示从 \(i\) 到 \(j\) 的所有路径中第一条边编号最大能是多少，这样子如果 \(a_{s,t}\ge l\)，那就说明询问是可以做到的，而转移的时候只需要把 \(a_{x,u}|a_{x,v}\) 改成 \(\max({a_{x,u},a_{x,v}})\) 即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 1005,M = 2e5+5,Q = 1e6+5;
int a[N][N],e[M][2],n,m,q;
bool ans[Q];
struct node{int l,r,s,t,id;}que[Q];
bool cmp(node x,node y){return x.r < y.r;}
inline int rd()
{
    char c;int f = 1;
    while(!isdigit(c = getchar()))if(c=='-')f = -1;
    int x = c-'0';
    while(isdigit(c = getchar()))x = x*10+(c^48);
    return x*f;
}
int main()
{
	n = rd();m = rd();q = rd();
	for(int i = 1;i <= m;i++)
		e[i][0] = rd(),e[i][1] = rd();
	for(int i = 1;i <= q;i++)
		que[i] = {rd(),rd(),rd(),rd(),i};
	sort(que+1,que+q+1,cmp);int now = 1;
	for(int i = 1;i <= m;i++)
	{
		int u = e[i][0],v = e[i][1];
		a[u][u] = i;a[v][v] = i;
		for(int j = 1;j <= n;j++)
			a[j][u] = a[j][v] = max(a[j][u],a[j][v]);
		for(node x;now <= q&&(x = que[now]).r <= i;now++)
			ans[x.id] = a[x.s][x.t] >= x.l;
	}
	for(int i = 1;i <= q;i++)puts(ans[i]?"Yes":"No");
    return 0;
}