4537: [Hnoi2016]最小公倍数
题意：一张边权无向图，多组询问u和v之间有没有一条a最大为a'，b最大为b'的路径(不一定是简单路径)
首先想到暴力做法，题目要求就是判断u和v连通，并查集把(a<a' land b<b')的边加入
然后想了一下特殊的莫队，不可做。不能按权值分块，因为同一个权值会有很多边，并且删除操作不好处理
发现这其实是一个偏序关系，但是无法用cdq分治，因为它要求所有满足偏序小的元素同时存在于某种组织形式中
使用分块
权值用((a,b))表示
边按a排序，然后分块。对于每一块i，处理a'在这一块中的询问。这时候之前块的(a<a')这一个关系一定满足，按b排序后也满足(b<b')了
块i中还有一些满足的，最多(sqrt{m}) 暴力加入然后撤销就可以了
不路径压缩的并查集，启发式合并的话复杂度log
注意是边权
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=2e5+5;
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, u, v, x, y, block, bn, top, ans[N];
struct meow {
int u, v, a, b, id;
inline void print() {printf("%d %d %d %d
", u, v, a, b);}
} e[N], q[N], a[N];
inline bool cmpa(const meow &a, const meow &b) {return a.a == b.a ? a.b < b.b : a.a < b.a;}
inline bool cmpb(const meow &a, const meow &b) {return a.b == b.b ? a.a < b.a : a.b < b.b;}
namespace ufs {
struct meow{int fa, maxa, maxb, size;} t[N];
struct info{int x, y; meow a, b; } st[N];
inline int find(int x) {return x == t[x].fa ? x : find(t[x].fa);}
inline void ini() {for(int i=1; i<=n; i++) t[i] = (meow){i, -1, -1, 1}; }
inline void link(int id) { //printf("link %d
", id);
int x = find(e[id].u), y = find(e[id].v);
st[++top] = (info){x, y, t[x], t[y]};
if(x==y) {
t[x].maxa = max(t[x].maxa, e[id].a);
t[x].maxb = max(t[x].maxb, e[id].b);
return;
}
if(t[x].size < t[y].size) swap(x, y);
t[y].fa = x;
t[x].maxa = max(max(t[y].maxa, t[x].maxa), e[id].a);
t[x].maxb = max(max(t[y].maxb, t[x].maxb), e[id].b);
t[x].size += t[y].size;
}
inline void recov() {
t[ st[top].x ] = st[top].a, t[ st[top].y ] = st[top].b;
top--;
}
inline bool check(int id) {
int x = find(a[id].u), y = find(a[id].v);
//printf("check %d %d %d %d %d %d
", id, x, y, t[x].maxa, t[x].maxb, t[x].size);
return x == y && t[x].maxa == a[id].a && t[x].maxb == a[id].b;
}
} using ufs::st;
void solve() {
sort(e+1, e+m+1, cmpa); sort(q+1, q+Q+1, cmpa);
block = sqrt(m); bn = (m-1)/block+1;
for(int i=1; i<=bn; i++) { //printf("
---------- %d
", i);
int l = (i-1)*block+1, r = i==bn ? m : i*block; //printf("[%d, %d]
", l, r);
int p=0;
for(int i=1; i<=Q; i++)
if(q[i].a >= e[l].a && (r==m || q[i].a < e[r+1].a) ) a[++p] = q[i];
sort(e+1, e+l, cmpb); sort(a+1, a+p+1, cmpb);
//for(int i=1; i<=p; i++) a[i].print();
int now=1;
ufs::ini();
for(int i=1; i<=p; i++) {
while(now < l && e[now].b <= a[i].b) ufs::link(now), now++;
top=0;
for(int j=l; j<=r; j++)
if(e[j].a <= a[i].a && e[j].b <= a[i].b) ufs::link(j);// printf("j %d
", j);
ans[ a[i].id ] = ufs::check(i);
while(top) ufs::recov();
}
}
for(int i=1; i<=Q; i++) puts(ans[i] ? "Yes" : "No");
}
int main() {
//freopen("in", "r", stdin);
freopen("multiple.in", "r", stdin);
freopen("multiple.out", "w", stdout);
n=read(); m=read();
for(int i=1; i<=m; i++) u=read(), v=read(), x=read(), y=read(), e[i] = (meow){u, v, x, y, i};
Q=read();
for(int i=1; i<=Q; i++) u=read(), v=read(), x=read(), y=read(), q[i] = (meow){u, v, x, y, i};
solve();
}