题意
题目链接
给出一张带权无向图，每次询问((u, v))之间是否存在一条路径满足(max(a) = A, max(b) = B)
Sol
这题居然是分块。。想不到想不到。。做这题的心路历程大概可以写个800字的作文。
(warning:)下面的做法复杂度是错的。但是可以过
以下是attack的心路历程
考场上不会做，然后看了一眼题解发现可以对(a)分块。
怎么分呢？我们可以对边按(a)分块，然后把每个询问先按(b)排序后扔到对应的(a)所在的块内
这个时候(b)的限制就好搞了，每个块都是递增的，之前的块可以预处理之后排序，复杂度(msqrt{m}log m)是可以接受的。
块内的呢？好像暴力就可以了，直接拿个启发式合并的可撤销带权并查集搞，维护一下路径最大值。复杂度也是(m sqrt{m} log m)，但是枚举的上界必须是(M)不然会wa((a)相同(b)不相同)，算了先交一发。。
然后交上去->80..
把T掉的数据下载下来发现居然有(a)全都相同的点。。。
emmmmmm，开始面向数据编程，每次询问的时候可以把每个块内询问(a)的最小值拿出来，按(b)排序之后双指针搞。
然后就过了，复杂度显然是不对的。只要来个(a)很小的数据就G了。
以下代码充满了attack对人生的思考，，，请谨慎观看
代码语言：javascript复制#include<bits/stdc .h>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
//#define int long long
#define LL long long
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int MAXN = 1e6 10, mod = 998244353, INF = 2e9 10;
const double eps = 1e-9;
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline LL add(A x, B y) {if(x y < 0) return x y mod; return x y >= mod ? x y - mod : x y;}
template <typename A, typename B> inline void add2(A &x, B y) {if(x y < 0) x = x y mod; else x = (x y >= mod ? x y - mod : x y);}
template <typename A, typename B> inline LL mul(A x, B y) {return 1ll * x * y % mod;}
template <typename A, typename B> inline void mul2(A &x, B y) {x = (1ll * x * y % mod mod) % mod;}
template <typename A> inline void debug(A a){cout << a << 'n';}
template <typename A> inline LL sqr(A x){return 1ll * x * x;}
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 c - '0', c = getchar();
return x * f;
}
int N, M, Q, block, belong[MAXN], ll[MAXN], rr[MAXN], mx, ans[MAXN];
struct Edge {
int u, v, a, b, id;
bool operator < (const Edge &rhs) const {
return a == rhs.a ? b < rhs.b : a < rhs.a;
}
}E[MAXN], q[MAXN], st[MAXN], fuck1[MAXN];
vector<Edge> fuck2;
int comp(const Edge &x, const Edge &y) {
return x.b == y.b ? x.a < y.a : x.b < y.b;
}
vector<Edge> v[MAXN];
int vis[MAXN], num, fa[MAXN], mxa[MAXN], mxb[MAXN], siz[MAXN];
struct Sta {
int x, ta, tb, si;
};
Sta inst[MAXN];
int find(int x) {
return fa[x] == x ? x : find(fa[x]);
}
void Add(Edge &e) {
int x = e.u, y = e.v, a = e.a, b = e.b;
int fx = find(x), fy = find(y);
if(fx == fy) {
inst[ num] = {fx, mxa[fx], mxb[fx], siz[fx]};
inst[ num] = {fy, mxa[fy], mxb[fy], siz[fy]};
chmax(mxa[fx], a); chmax(mxb[fx], b);
return ;
}
if(siz[fx] > siz[fy]) swap(fx, fy), swap(x, y);
inst[ num] = {fx, mxa[fx], mxb[fx], siz[fx]};
inst[ num] = {fy, mxa[fy], mxb[fy], siz[fy]};
siz[fy] = siz[fx];
chmax(mxa[fy], a); chmax(mxb[fy], b);
chmax(mxa[fy], mxa[fx]); chmax(mxb[fy], mxb[fx]);
fa[fx] = fy;
}
void Erase(int tim) {
while(num > tim) {
Sta pre = inst[num--];
fa[pre.x] = pre.x; mxa[pre.x] = pre.ta; mxb[pre.x] = pre.tb; siz[pre.x] = pre.si;
}
}
void solve() {
int top = 0;
for(int i = 1; i <= N; i ) fa[i] = i, siz[i] = 1, mxa[i] = mxb[i] = -1;
for(int i = 1; i <= mx; i ) {
int now = 1; int gg = num, fucknum = 0, mn = INF; fuck2.clear();
for(auto &x : v[i]) chmin(mn, x.a);
for(int j = ll[i]; j <= M; j )
if(E[j].a <= mn) fuck1[ fucknum] = E[j];
else fuck2.push_back(E[j]);
sort(fuck1 1, fuck1 fucknum 1, comp);
int cur = 0;
for(auto &x : v[i]) {
while(now <= top && st[now].b <= x.b) Add(st[now ]);
while(cur <= fucknum && fuck1[cur].b <= x.b) Add(fuck1[cur ]);
int tmp = num;
for(auto & j : fuck2) {
if(j.a <= x.a ) {
if(j.b <= x.b) {
Add(j);
}
} else break;
}
int fx = find(x.u), fy = find(x.v);
if(fx != fy || mxa[fx] != x.a || mxb[fx] != x.b) ans[x.id] = 2;
else ans[x.id] = 1;
Erase(tmp);
}
Erase(gg);
for(int j = ll[i]; j <= rr[i]; j ) st[ top] = E[j];
sort(st 1, st top 1, comp);//�Ѿ�����İ�b�ź���ı�
}
}
signed main() {
// Fin(a); Fout(b);
N = read(); M = read(); block = sqrt(M * log(M));
for(int i = 1; i <= M; i ) E[i].u = read(), E[i].v = read(), E[i].a = read(), E[i].b = read();
E[ M] = {-1, -1, INF, INF};
sort(E 1, E M 1);
for(int i = 1; i <= M; i ) belong[i] = (i - 1) / block 1, chmax(mx, belong[i]);
for(int i = 1; i <= mx; i ) ll[i] = (i - 1) * block 1, rr[i] = min(M, ll[i] block - 1);//tag
Q = read();
for(int i = 1; i <= Q; i ) q[i].u = read(), q[i].v = read(), q[i].a = read(), q[i].b = read(), q[i].id = i;
sort(q 1, q Q 1, comp);
for(int i = 1; i <= Q; i ) {
int pos = lower_bound(E 1, E M 1, q[i]) - E;
v[belong[pos]].push_back(q[i]);
}
solve();
for(int i = 1; i <= Q; i ) puts(ans[i] == 1 ? "Yes" : "No");
return 0;
}
