学习笔记：图论算法

f2021ljh's blog / 2023-05-19 / 原文

参考资料

高级图论 - qAlex_Weiq - 博客园
简单树论 - qAlex_Weiq - 博客园

2-SAT

SAT 的定义

该部分与 OI 没有太大关系，不感兴趣的读者可以跳过。

为方便说明，首先给出相关术语。

合取：用符号 \(\wedge\) 表示，是自然语言联结词 “且” 的抽象。命题 \(p\wedge q\) 表示 \(p,q\) 的合取，称为合取式，读作 \(p\) 且 \(q\)，其为真当且仅当 \(p,q\) 均为真。简单地说，合取就是逻辑与 &&，可以类比计算机科学中的按位与 &，相信这个概念大家并不陌生。

析取：用符号 \(\vee\) 表示，是自然语言联结词 “或” 的抽象。命题 \(p\vee q\) 表示 \(p,q\) 的析取，称为析取式，读作 \(p\) 或 \(q\)，其为真当且仅当 \(p,q\) 至少有一个为真。同样的，合取是逻辑或 ||，类比按位或 |。

否定：用符号 \(\lnot\) 表示，\(\lnot p\) 表示命题 \(p\) 的否定，其真假性与 \(p\) 相反。否定是逻辑非 !，类比按位取反 ~。

上述三条概念均为基本命题联结词，大概可以看作给常见的 “与或非” 三种运算起了高大上的名字。将命题变元（可真可假的布尔变量）用合取 \(\wedge\)，析取 \(\vee\) 和否定 \(\lnot\) 联结在一起，得到布尔逻辑式（叫法不唯一）。

布尔逻辑式可满足，指存在一个对所有命题变元的真假赋值，使得该布尔逻辑式为真。

布尔可满足性问题（Boolean Satisfiability Problem）简称 SAT，它定义为检查一个布尔逻辑式是否可满足，是第一个被证明的 NPC 问题。

命题变元或其否定称为文字。

若干个文字的析取称为简单析取式，形如 \(P=x_1\vee x_2\vee\dots\vee x_k\)，其中 \(x_i\) 表示命题 \(p_i\) 或其否定 \(\lnot p_i\)。

若干简单析取式的合取称为合取范式（Conjunctive Normal Form，CNF），形如 \(P_1\wedge P_2\wedge\dots\wedge P_n\)，其中 \(P_i\) 表示一个简单析取式。

考虑 SAT 的简单版本：命题公式为合取范式，且组成它的每个简单析取式至多含有 \(k\) 个文字。这一问题称为 \(k\)-SAT。

当 \(k\ge3\) 时 \(k\)-SAT 是 NPC 问题，但 2-SAT 存在多项式复杂度的解法。接下来介绍这一算法。

2-SAT 算法

我们可以将 2-SAT 看作一组需要同时为真的条件，每个条件可能的形态为：\(p\)，\(\lnot p\)，\(p\vee q\)，\(p\vee\lnot q\)，\(\lnot p\vee\lnot q\)。

注意到每个条件至多与两个文字（布尔变量）有关，这启发我们转化为图论问题。

可以用一条有向边 \(p\to q\) 表示 “若 \(p\) 则 \(q\)” 的条件。那么有：

条件（简单析取式）	自然语言	充分条件形式命题
\(p\)	\(p\) 为真	若 \(\lnot p\) 则 \(p\)
\(\lnot p\)	\(p\) 为假	若 \(p\) 则 \(\lnot p\)
\(p\vee q\)	\(p\) 和 \(q\) 至少有一个为真	若 \(\lnot p\) 则 \(q\)，若 \(\lnot q\) 则 \(p\)
\(p\vee\lnot q\)	\(p\) 和 \(\lnot q\) 至少有一个为真	若 \(\lnot p\) 则 \(\lnot q\)，若 \(q\) 则 \(p\)
\(\lnot p\vee\lnot q\)	\(\lnot p\) 和 \(\lnot q\) 至少有一个为真	若 \(p\) 则 \(\lnot q\)，若 \(q\) 则 \(\lnot p\)

注意命题的 逆否命题 也成立。

我们对每个布尔变量 \(p\) 在图中建出两个点表示 \(p\) 和 \(\lnot p\)。根据所有条件建出有向图后，一条路径 \(p\leadsto q\) 就表示命题 \(p\implies q\)。

首先我们考虑无解的情况。根据第一、二种条件，如果存在路径 \(\lnot p\leadsto p\) 则 \(p\) 一定为真，如果存在路径 \(p\leadsto\lnot p\) 则 \(p\) 一定为假。进一步地，若 \(p\) 和 \(\lnot p\) 强连通，则该 2-SAT 问题无解。于是缩点即可判断无解的充分条件。

除此之外，我们考虑是否一定有解。对于一个变元 \(p\)，布尔式 \(p\) 和 \(\lnot p\) 一定有且仅有一个为真，对应变元 \(p\) 为真或假。因此，在图中，如果我们设 \(P\) 为我们钦定布尔值为真的 \(n\) 个节点构成的集合，那么一定不存在某个 \(p_0\) 和 \(\lnot p_0\)，同时能被 \(P\) 中任意的某些点到达。所以，\(P\) 中所有点能到达的点恰有 \(n\) 个，即 \(P\) 导出的子图是一个闭合子图。也就是说，如果 \(p\) 和 \(p'\) 为真，那么 \(p\) 一定不可能到达 \(\lnot p'\)，反之亦然。

接下来尝试构造一组解。对于缩点后的图，若 \(\lnot p\) 能到达 \(p\)，即 \(p\) 的拓扑序一定在 \(\lnot p\) 后面，则 \(p\) 为真。所以对于每个布尔变元 \(p\)，可以考虑选择 \(p\) 和 \(\lnot p\) 中拓扑序较大的一个设为真。

证明　反证法。假设存在 \(p\) 和 \(q\) 满足拓扑序 \(p>\lnot p,q>\lnot q\)（即按照上面的规则 \(p,q\) 为真），而 \(p\) 能到达 \(\lnot q\)，即 \(p\implies\lnot q\)。那么它的逆否命题成立，即 \(q\implies\lnot p\)。考虑拓扑序大小，有 \(p<\lnot q<q\)，且 \(q<\lnot p<p\)，矛盾。于是选择拓扑序较大的设为真，一定不存在不合法的情况。

因此，解一定存在，并且我们可以构造出某一组合法的解，构造方法即为：将 \(p\) 和 \(\lnot p\) 中 拓扑序较大 的设为真。

注意到在用 Tarjan 算法缩点的过程中，我们已经得到了缩点后 DAG 的反向拓扑序：若 \(u\) 能到达 \(v\)，则 \(v\) 在 \(u\) 之前从栈中被弹出，即 SCC 的编号 sccid[v] < sccid[u]，因此我们只需要在 \(p\) 和 \(\lnot p\) 中选择 sccid 较小的设为真。

时间复杂度 \(O(n+m)\)。

例题

P4782 【模板】2-SAT 问题

#include <stack>
#include <iostream>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
using namespace std;
int constexpr N = 2e6 + 10;
int n, m, ans[N >> 1];

int head[N], cnt;
struct Edge {
    int to, nxt;
} e[N << 1];
inline void add(int from, int to) {
    e[++cnt].to = to, e[cnt].nxt = head[from], head[from] = cnt;
    return;
}

int dfn[N], low[N], tot;
int sccid[N], num;
stack<int> st;
bool in[N];
void Tarjan(int u) {
    dfn[u] = low[u] = ++tot;
    st.push(u), in[u] = true;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (!dfn[v]) {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++num;
        while (!st.empty()) {
            int t = st.top();
            st.pop(), in[t] = false;
            sccid[t] = num;
            if (t == u) break;
        }
    }
    return;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin >> n >> m;
    int x, y, a, b;
    f(i, 1, m) {
        cin >> x >> a >> y >> b;
        add(x + n * a, y + n * (!b));
        add(y + n * b, x + n * (!a));
    }
    f(i, 1, n << 1) if (!dfn[i]) Tarjan(i);
    f(i, 1, n) {
        if (sccid[i] == sccid[i + n]) return cout << "IMPOSSIBLE\n", 0;
        ans[i] = (sccid[i] < sccid[i + n]);
    }
    cout << "POSSIBLE\n";
    f(i, 1, n) cout << ans[i] << ' ';
    
    return 0;
}

LOJ 3629 「2021 集训队互测」序列

有一个长度为 \(n\) 的序列 \(a_1,a_2,\dots,a_n\)，序列里的每个元素都是 \([1,10^9]\) 内的正整数。

现在已知了 \(m\) 条信息，每条信息形如 \(i,j,k,x\)，表示这个序列满足 \(a_i+a_j+a_k−\max(a_i,a_j,a_k)−\min(a_i,a_j,a_k)=x\)。

请构造一个满足条件的序列。

对于全部数据，\(1≤n,m≤10^5,1≤i,j,k≤n,1≤x≤10^9\)。

首先把条件转化一下，可以发现这个条件的意思就是 \(\{a_i,a_j,a_k\}\) 的中位数等于 \(x\)。

~~注意到题目的标签中有 2-SAT，~~ ~~注意到这个题出现在 2-SAT 专题中，~~

那么我们怎么把条件转化为 2-SAT 中的 二元条件 呢？

不妨先设 \(a_i<x\)，那么有 \(a_j\ge x\) 且 \(a_k\ge x\)。同理有 \(a_j<x\implies a_i\ge x,a_k\ge x\)，\(a_k<x\implies a_i\ge x,a_j\ge x\)。

我们设布尔变元 \(p(i,x)=[a_i\ge x]\)。那么有

\[\begin{aligned} \lnot p(i,x)\implies p(j,x),p(k,x),\\ \lnot p(j,x)\implies p(i,x),p(k,x),\\ \lnot p(k,x)\implies p(i,x),p(j,x). \end{aligned} \]

按 2-SAT 算法建边即可。

但是注意有 隐含条件：如果 \(a_i\ge x_1\)，并且 \(x_1>x_2\)，那么 \(a_i\ge x_2\)。

所以对于每一组相邻的 \(x_1,x_2\)，有 \(p(i,x_1)\implies p(i,x_2)\)。“相邻的” 是指在 \(x\) 的离散化数组中相邻。不需要对于每一组 \(x_1,x_2\) 都建边，因为可以推导过去（在图上就体现为能到达）。

执行完 2-SAT 算法之后，我们得到了一组 \(p\) 的值。对于一个 \(a_i\)，二分找出相邻的 \(s<t\) 满足 \(p(a_i,s)\) 为真，\(p(a_i,t)\) 为假。令 \(a_i=s\) 即为一组答案。

xbc 到此一游：其实不一定，对于一个 \(i\)，可能所有的 \(x\) 都满足 \(p(i, x)\) 是真的，或者所有都是假的。

原题的条件是要令 \(a_i \in \left[1, 10^9\right]\)，因此，对于一个 \(i\)，

如果所有 \(p(i, x_j)\) 都是真的，将 \(a_i\) 设成 \(10^9\) 即可；

而如果所有 \(p(i, x_j)\) 都是假的，看这些 \(x\) 中有没有出现 \(1\)，如果出现 \(1\)（即能推出 \(p(i, 1)\) 为假）问题就无解，否则直接将 \(a_i\) 设成 \(1\) 即可。

代码不会写。

Kruskal 重构树

构建

首先考虑 Kruskal 算法的实现过程：按边权从小到大遍历每条边 \((u,v)\)，根据贪心思想，如果 \(u\) 和 \(v\) 当前未通过边权更小的边连通，就将当前边加入最小生成树，并且连接 \(u\) 和 \(v\)。使用并查集维护连通性。

但是有时候，我们会遇到有 边权限制 的问题，并且数据范围不允许暴力跑多次 Kruskal。

注意到，Kruskal 越往后加的边权越大。所以可以用某种数据结构维护加入边的顺序，以刻画边权有限制时图的连通情况。

Kruskal 重构树 的构建过程：

连接 \(u,v\) 时，找到当前 \(u,v\) 的 代表元 \(U,V\)。新建节点 \(c\)，在重构树 \(T\) 上设 \(c\) 为 \(U,V\) 的父亲。注意 \(U,V\) 可能不是原图中的节点，而是设置的虚点。

通常设 \(c\) 的权值 \(w_c=w_{u,v}\)。为虚点设置权值方便解题，巧妙设置点权对解题有极大帮助。

性质

设原图 \(G\) 的 Kruskal 重构树为 \(T\)。Kruskal 重构树有很多优秀性质：

\(T\) 是一棵二叉树。对于部分题目，特殊的重构树建法可以有效减小常数。
\(T\) 的叶子对应于 \(G\) 的所有 \(n\) 个节点，\(T\) 的其他节点对应于 \(G\) 的 MST 的 \(n-1\) 条边。\(T\) 共有 \(2n-1\) 个节点。
对于任意 \(T\) 中节点 \(u\)，\(v\) 是 \(u\) 的祖先，则有 \(w_u\le w_v\)。即父亲权值大于儿子权值。

其中，性质 3 尤其重要。它是 Kruskal 重构树的核心：

如果边权限制 \(\le d\)，那么节点 \(x\) 可达的所有点就是它在 \(T\) 上的权值 \(\le d\) 的最浅祖先 \(a\) 的子树内的所有叶子节点。

于是我们可以倍增求解 \(a\)。

综上，我们可以总结出一个常用套路：当题目限制形如 “只经过权值不大于某个值的点或边” 时，从 Kruskal 重构树角度入手。

部分题目也可以在 Kruskal 过程中将并查集可持久化，以刻画边权有限制时图的连通情况，但时空复杂度更劣，不建议使用。

例题

P4768 [NOI2018] 归程

\(T\) 组数据。每组数据给定一张 \(n\) 个点 \(m\) 条边的无向图，边有两个参数：长度 \(l\) 和海拔 \(a\)。每组数据 \(Q\) 次询问，每次询问给定出发点 \(v\) 和水位线 \(p\)，其中海拔不超过水位线的边有积水，从出发点 \(v\) 可以驾车通过任意没有积水的边，之后步行到达节点 \(1\)。每次询问输出最小的步行经过的边的总长度。部分测试点强制在线。

\(n\le2\times10^5\)，\(m\le4\times10^5\)，\(Q\le4\times10^5\)，可能的最高水位线 \(S\le10^9\)。对于所有边，\(1\le l\le10^4\)，\(1\le a\le10^9\)。

设 \(d_i\) 为从点 \(i\) 到点 \(1\) 的最短路长度，\(V\) 为从点 \(v\) 驾车能到达的所有点，那么答案即为 \(\min_{i\in V}d_i\)。

驾车能通过的边即为海拔 \(a\) 大于水位线 \(p\) 的边。

考虑用 Kruskal 重构树快速查找从点 \(v\) 出发，只经过海拔大于 \(p\) 的边能到达的所有点。

具体地，将边按 \(a\) 从大到小排序（海拔越大越不可能有积水），建出 Kruskal 重构树 \(T\)，从点 \(v\) 对应的叶子节点向上倍增，找到深度最浅的祖先 \(A\) 满足海拔大于 \(p\)。那么以 \(A\) 为根的子树内所有的叶子节点都可以到达。dfs 处理倍增数组的同时，记录子树内叶子节点的 \(d\) 的最小值，即可快速得到 \(A\) 的答案。

注意数组范围的细节。

#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
#define g(x, y, z) for (int x = (y); x >= (z); --x)
using namespace std;
typedef pair<int, int> pii;
int constexpr N = 2e5 + 10, M = 4e5 + 10;
int T, n, m, lg, Q, K, S;

vector<pii> e[N];

struct Edge {
    int u, v, a, l;
    inline void read() {
        cin >> u >> v >> l >> a;
        e[u].emplace_back(v, l);
        e[v].emplace_back(u, l);
        return;
    }
} edge[M], tree[N << 1];

int L[N << 1], R[N << 1], num;

int fa[N << 1];
int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); }
inline bool cmp(Edge const &_1, Edge const &_2) { return _1.a > _2.a; }
void Kruskal() {
    num = n;
    f(i, 1, n) fa[i] = i, L[i] = R[i] = 0;
    f(i, n + 1, n * 2 - 1) fa[i] = i;
    sort(edge + 1, edge + m + 1, cmp);
    int cnt = 0;
    f(i, 1, m) {
        int fu = getfa(edge[i].u), fv = getfa(edge[i].v);
        if (fu ^ fv) {
            ++num;
            L[num] = fu, R[num] = fv;
            fa[fu] = fa[fv] = num;
            tree[num].a = edge[i].a;
            if (++cnt == n - 1) break;
        }
    }
    return;
}

priority_queue<pii> q;
bool vis[N];
int d[N];
void Dijkstra(int s = 1) {
    memset(d, 0x3f, sizeof d);
    memset(vis, 0, sizeof vis);
    d[s] = 0;
    q.emplace(0, s);
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (pii i: e[u]) {
            int v = i.first, w = i.second;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                q.emplace(-d[v], v);
            }
        }
    }
    return;
}

int f[19][N << 1], mn[N << 1];
void dfs(int u, int fa) {
    f[0][u] = fa;
    f(i, 1, lg) f[i][u] = f[i - 1][f[i - 1][u]];
    if (!L[u] && !R[u]) return mn[u] = d[u], void();
    dfs(L[u], u), dfs(R[u], u);
    mn[u] = min(mn[L[u]], mn[R[u]]);
    return;
}

int query(int v, int p) {
    g(i, lg, 0) if (f[i][v] && tree[f[i][v]].a > p) v = f[i][v];
    return mn[v];
}

void Init() {
    f(i, 1, n) e[i].clear();
    return;
}

void solve() {
    Init();
    cin >> n >> m;
    lg = __builtin_log2(n);
    f(i, 1, m) edge[i].read();
    Kruskal();
    Dijkstra();
    dfs(num, 0);
    cin >> Q >> K >> S;
    int v0, p0, v, p, ans = 0;
    while (Q--) {
        cin >> v0 >> p0;
        v = (v0 + K * ans - 1) % n + 1;
        p = (p0 + K * ans) % (S + 1);
        cout << (ans = query(v, p)) << '\n';
    }
    return;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin >> T;
    while (T--) solve();
    
    return 0;
}

P4899 [IOI2018] werewolf 狼人

给定一张 \(N\) 个点 \(M\) 条边的无向图，点的编号从 \(0\) 到 \(N-1\)。\(Q\) 次询问，每次询问给定 \(S,E,L,R\)，问能否从 \(S\) 到达 \(E\)，且路径满足如下限制：

把整条路径分成三段，第一段必须避开点 \(0,1,\dots,L-1\)，第二段为 \(L,L+1,\dots,R\) 中的某一个点，第三段必须避开点 \(R+1,R+2,\dots,N-1\)。

\(2\le N\le200000\)，\(N-1\le M\le400000\)，\(1\le Q\le200000\)。

下面将节点编号、\(L\)、\(R\) 加一。

题目意思其实就是：从 \(S\) 出发只能经过编号 \([L,N]\) 范围内的点，能到达的点集设为 \(V_1\)；从 \(E\) 出发只能经过编号在 \([1,R]\) 范围内的点，能到达的点集设为 \(V_2\)。问是否存在点同时包含于 \(V_1\) 和 \(V_2\)。

我们把编号看作点的权值（其实原题的题面中有提示），那么题意就转化为：限制经过点的点权，求从某点出发能到达的点的集合，然后再求两个这样的集合是否有交集。这样就可以考虑用 Kruskal 重构树解决。

题目中分别限制了权值不小于 \(L\) 和权值不大于 \(R\)，于是我们建出两棵 Kruskal 重构树 \(T_1,T_2\)，设边 \((u,v)\) 的权值分别为 \(\boldsymbol{\min(u,v)}\) 和 \(\boldsymbol{\max(u,v)}\)，分别按权从大到小和从小到大排序并建树。

在 \(T_1\) 上从 \(S\) 向上倍增，容易求出权值不小于 \(L\) 的 \(S\) 的最浅祖先 \(A_1\)，那么从 \(S\) 出发经过点权不小于 \(L\) 的点能到达的所有点的集合 \(V_1\)，即为 \(T_1\) 上以 \(A_1\) 为根的子树中的所有叶子节点。同理求出从 \(E\) 出发经过点权不大于 \(R\) 的点能到达的所有点的集合 \(V_2\)。

接下来的问题就只剩下如何求 \(V_1\) 和 \(V_2\) 是否有交。

将 \(T_1\) 的所有叶子按 dfn 序从小到大排序，得到的是一个 \(1\) 到 \(N\) 的排列，记为 \(p_1\)。

由于我们求得的是一棵子树内的所有叶子，这些叶子在 \(p_1\) 上必然是连续的一段。

同理，将 \(T_2\) 的所有叶子按 dfn 序从小到大排序得到 \(p_2\)，那么我们求得的叶子在 \(p_2\) 上也是连续的一段。

于是就变成了：给两个 \(1\) 到 \(N\) 的排列 \(p_1,p_2\)，多次询问集合 \(\{{p_1}_{l_1},{p_1}_{l_1+1},\dots,{p_1}_{r_1}\}\) 与 \(\{{p_2}_{l_2},{p_2}_{l_2+1},\dots,{p_2}_{r_2}\}\) 是否有交。

这是一个二维数点问题，由于这是两个排列，我们把每个数 \(x\) 在 \(p_1\) 和 \(p_2\) 中出现的位置记为 \((a_x,b_x)\)，那么询问的就是在二维平面上以 \(\boldsymbol{(l_1,l_2),(r_1,r_2)}\) 为左下角和右上角的矩形内是否有点。

洛谷上这题没有强制在线，我们可以把询问离线下来，然后用树状数组实现二维数点。

#include <iostream>
#include <algorithm>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
#define g(x, y, z) for (int x = (y); x >= (z); --x)
using namespace std;
int constexpr N = 2e5 + 10, M = 4e5 + 10;
int n, m, qq, lg;

struct Edge {
    int u, v, mn, mx;
} edge[M];

inline bool cmp1(Edge const &p, Edge const &q) {
    return p.mn > q.mn;
}
inline bool cmp2(Edge const &p, Edge const &q) {
    return p.mx < q.mx;
}

struct Kruskal { //重构树
    int L[N << 1], R[N << 1], num, val[N << 1];
    bool fl;

    int f[20][N << 1];
    int a[N], l[N << 1], r[N << 1], tot;
    void dfs(int u, int fa) {
        f[0][u] = fa;
        f(i, 1, lg) f[i][u] = f[i - 1][f[i - 1][u]];
        if (!L[u] && !R[u]) {
            a[++tot] = u; //将所有叶子拍平在序列上(按 dfn 序)
            l[u] = r[u] = tot;
            return;
        }
        dfs(L[u], u), dfs(R[u], u);
        l[u] = l[L[u]], r[u] = r[R[u]]; //子树内叶子在序列上的最小和最大编号
        return;
    }

    int fa[N << 1];
    int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); }
    void build() {
        num = n;
        f(i, 1, n) fa[i] = val[i] = i, L[i] = R[i] = 0;
        f(i, n + 1, n << 1) fa[i] = i;
        sort(edge + 1, edge + m + 1, fl ? cmp2 : cmp1);
        int cnt = 0;
        f(i, 1, m) {
            int fu = getfa(edge[i].u), fv = getfa(edge[i].v);
            if (fu ^ fv) {
                ++num;
                val[num] = fl ? edge[i].mx : edge[i].mn;
                // val[num] = fl ? max(val[fu], val[fv]) : min(val[fu], val[fv]);
                L[num] = fu, R[num] = fv;
                fa[fu] = fa[fv] = num;
                if (++cnt == n - 1) break;
            }
        }
        dfs(num, 0);
        return;
    }

} kk1, kk2;

struct Node { //平面上的点
    int a, b;
    inline bool operator<(Node const &o) const {
        return a == o.a ? b < o.b : a < o.a;
    }
} node[N];

int c;
struct Point { //二维数点的询问点
    int x, y, c, id;
    Point() {}
    Point(int _x, int _y, int _c, int _id): x(_x), y(_y), c(_c), id(_id) {}
    inline bool operator<(Point const &o) const {
        return x == o.x ? y < o.y : x < o.x;
    }
} q[N << 2];

struct BIT {
    int c[N];
    inline int lb(int const &x) { return x & (-x); }
    void add(int x) { while (x <= n) ++c[x], x += lb(x); };
    int sum(int x) { int r = 0; while (x) r += c[x], x -= lb(x); return r; }
} T;

struct Query { //离线询问
    int S, E, L, R, ans;
    inline void read(int id) {
        cin >> S >> E >> L >> R;
        ++S, ++E, ++L, ++R;
        g(i, lg, 0) {
            int t = kk1.f[i][S];
            if (t && kk1.val[t] >= L) S = t;
        }
        int l1 = kk1.l[S], l2 = kk1.r[S];
        g(i, lg, 0) {
            int t = kk2.f[i][E];
            if (t && kk2.val[t] <= R) E = t;
        }
        int r1 = kk2.l[E], r2 = kk2.r[E];
        q[++c] = Point(l1 - 1, r1 - 1, 1, id);
        q[++c] = Point(l1 - 1, r2, -1, id);
        q[++ c] = Point(l2, r1 - 1, -1, id);
        q[++c] = Point(l2, r2, 1, id);
        return;
    }
} Q[N];
int pos[N];

void solve() {
    sort(q + 1, q + c + 1);
    sort(node + 1, node + n + 1);
    int cur = 1;
    f(i, 1, c) {
        while (cur <= n && node[cur].a <= q[i].x)
            T.add(node[cur].b), ++cur;
        Q[q[i].id].ans += T.sum(q[i].y) * q[i].c;
    }
    return;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    kk1.fl = 0, kk2.fl = 1;
    cin >> n >> m >> qq;
    lg = __builtin_log2(n);
    f(i, 1, m) {
        cin >> edge[i].u >> edge[i].v;
        ++edge[i].u, ++edge[i].v;
        edge[i].mn = min(edge[i].u, edge[i].v);
        edge[i].mx = max(edge[i].u, edge[i].v);
    }
    kk1.build(), kk2.build();
    f(i, 1, n) node[kk1.a[i]].a = node[kk2.a[i]].b = i;
    f(i, 1, qq) Q[i].read(i);
    solve();
    f(i, 1, qq) cout << (Q[i].ans ? 1 : 0) << '\n';
    
    return 0;
}