现在看这题已经是时代的眼泪了啊。。。
首先分别从大到小和从小到大建立两棵重构树，每次在重构树上倍增，它的子树里的点就分别是从起点走 \(L\) 到 \(n\) 中的点能到的点和从终点走 \(1\) 到 \(R\) 中的点能到的点。我们可以轻松地用dfs序把它们弄到两个序列的区间上面。
问题就转化成了每次给两个排列上的两个区间判断是否有相同的数，这是个二维数点问题，直接主席树解决了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m, q;
const int N = 200005;
inline int min_(int a, int b) {
return a < b ? a : b;
}
inline int max_(int a, int b) {
return a > b ? a : b;
}
class Tree {
int en;
struct edge {
int head, to, nxt;
} ed[N << 1];
inline void add_edge(int from, int to) {
ed[++en].to = to; ed[en].nxt = ed[from].head; ed[from].head = en;
}
public :
int fa[N << 1][20], root, dfn[N], tim, arr[N], L[N << 1], R[N << 1], val[N << 1];
Tree() { tim = 0; en = 0; }
inline void addedge(int u, int v) {
add_edge(u, v);
}
inline void dfs(int now, int f) {
fa[now][0] = f; L[now] = 0x3f3f3f3f; R[now] = -1;
if (now <= n) {
arr[dfn[now] = ++tim] = now;
L[now] = R[now] = tim;
}
for (int i = 1; i < 20; ++i) fa[now][i] = fa[fa[now][i - 1]][i - 1];
for (int i = ed[now].head; i; i = ed[i].nxt) {
dfs(ed[i].to, now); L[now] = min_(L[now], L[ed[i].to]);
R[now] = max_(R[now], R[ed[i].to]);
}
}
};
Tree t1, t2;
struct edge {
int from, to, val;
} ed[N << 1];
inline bool cmp2(edge a, edge b) {
return a.val > b.val;
}
inline bool cmp1(edge a, edge b) {
return a.val < b.val;
}
int f[N << 1];
inline int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
inline void kruskal1() {
for (int i = 1; i <= n << 1; ++i) f[i] = i;
for (int i = 1; i <= n; ++i) t1.val[i] = i;
for (int i = 1; i <= m; ++i) ed[i].val = min_(ed[i].from, ed[i].to);
t1.root = n;
sort(ed + 1, ed + m + 1, cmp2);
for (int i = 1; i <= m; ++i) {
int fu = find(ed[i].from), fv = find(ed[i].to);
if (fu == fv) continue;
t1.addedge(++t1.root, fu); t1.addedge(t1.root, fv);
t1.val[t1.root] = ed[i].val;
f[fu] = f[fv] = t1.root;
}
}
inline void kruskal2() {
for (int i = 1; i <= n << 1; ++i) f[i] = i;
for (int i = 1; i <= n; ++i) t2.val[i] = i;
for (int i = 1; i <= m; ++i) ed[i].val = max_(ed[i].from, ed[i].to);
t2.root = n;
sort(ed + 1, ed + m + 1, cmp1);
for (int i = 1; i <= m; ++i) {
int fu = find(ed[i].from), fv = find(ed[i].to);
if (fu == fv) continue;
t2.addedge(++t2.root, fu); t2.addedge(t2.root, fv);
t2.val[t2.root] = ed[i].val;
f[fu] = f[fv] = t2.root;
}
}
struct node {
int sum;
node *right = NULL;
node *left = NULL;
} mem[N * 20];
node *root[N];
int top = 0;
inline node* newNode(node *t) {
node *rt = &mem[++top]; rt -> sum = t -> sum; return rt;
}
inline void build(node *now, int l, int r) {
now -> sum = 0;
if (l >= r) return ;
now -> left = &mem[++top]; build(now -> left, l, l + r >> 1);
now -> right = &mem[++top]; build(now -> right, (l + r >> 1) + 1, r);
}
inline node* insert(node *now, node *rt, int l, int r, int k) {
rt = newNode(now); rt -> sum++;
if (l < r) {
int mid = l + r >> 1;
if (k <= mid) {
rt -> left = insert(now -> left, rt -> left, l, mid, k);
rt -> right = now -> right;
} else {
rt -> right = insert(now -> right, rt -> right, mid + 1, r, k);
rt -> left = now -> left;
}
} return rt;
}
inline int query(node *now, int l, int r, int ql, int qr) {
if (now -> sum == 0) return 0;
if (ql <= l && r <= qr) return now -> sum;
int mid = l + r >> 1, ret = 0;
if (now -> left != NULL && ql <= mid) ret = query(now -> left, l, mid, ql, qr);
if (now -> right != NULL && qr > mid) ret += query(now -> right, mid + 1, r, ql, qr);
return ret;
}
inline int read() {
register int s = 0;
register char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch & 15), ch = getchar();
return s;
}
int main() {
n = read(); m = read(); q = read();
for (int i = 1; i <= m; ++i) {
ed[i].from = read() + 1; ed[i].to = read() + 1;
} kruskal1(); kruskal2(); t1.dfs(t1.root, 0); t2.dfs(t2.root, 0);
root[0] = &mem[++top]; build(root[0], 1, n);
for (int i = 1; i <= n; ++i) {
root[i] = insert(root[i - 1], root[i], 1, n, t2.dfn[t1.arr[i]]);
} int l, r, u, v;
while (q--) {
u = read() + 1; v = read() + 1; l = read() + 1; r = read() + 1;
int x = u, y = v;
for (int i = 19; ~i; --i) {
if (t1.val[t1.fa[x][i]] >= l && t1.fa[x][i] != 0) x = t1.fa[x][i];
}
for (int i = 19; ~i; --i)
if (t2.val[t2.fa[y][i]] <= r && t2.fa[y][i] != 0) y = t2.fa[y][i];
puts(query(root[t1.R[x]], 1, n, t2.L[y], t2.R[y]) > query(root[t1.L[x] - 1], 1, n, t2.L[y], t2.R[y]) ? "1" : "0");
} return 0;
}