题解

思路概述

• 交互库要求维护若干以中序序列为主体的二叉树，支持“拼接”“分裂”“访问”。实现上把每棵树视为一棵 Treap：节点随机权重（rnd）保证平衡，其中中序遍历正好对应序列顺序。
• join(x,y)：把两棵 Treap 依据随机权重合并，并记录合并过程中的操作（通过 move 接口通知评测环境更改结构）。最终得到的新根赋给编号 tot+1，并返回新树两个手下对应的旧结点编号。
• split(x,k)：把 Treap x 按中序第 k 个位置拆成两棵。通过递归调整随机权重并调用 move 修改儿子指针，实现“权重 Treap + 中序第 k 个节点”分割，返回新树手下所在的节点编号。
• visit(x)：访问时需要把树恢复为“合法的 Treap 形态”，代码会针对当前根不断旋转/调整子树，使得所有祖先都被重新连回 Treap，并返回根节点编号。

说明

• 树上维护的每个节点含左右儿子指针、父指针、子树大小等信息；为了让交互库同步结构，所有结构修改都体现为 move() 调用：移动工人到指定节点并调整儿子指针，同时浇水恢复节点状态。
• maxdep、maxcnt 限制靠随机权重 Treap 保证平衡，确保单次 join/split/visit 的 move 次数不超过限制。

复杂度

• Treap 操作期望 O(log n)；整套解法在交互库的限制下可以顺利运行。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000001;
int n, m, q, qx, qy, cnt, tot, ptt, head[N], du[N], bl[N], x[N], y[N], L[N], R[N], lc[N];
int lf[N], rf[N];
struct dcz {
    int nex, to;
} a[2 * N];
void add(int x, int y) {
    a[++cnt].nex = head[x];
    a[cnt].to = y;
    head[x] = cnt;
}
void solve(int x) {
    L[x] = lf[x], R[x] = rf[x];

    while (1) {
        bool f = 0;
        ptt++;
        assert(ptt < 2e8);

        if (R[x] < n && lc[R[x]] <= R[x] && lc[R[x]] >= L[x]) {
            f = 1;
            R[x] = R[bl[R[x] + 1]];
        }

        if (L[x] > 1 && lc[L[x] - 1] <= R[x] && lc[L[x] - 1] >= L[x]) {
            f = 1;
            L[x] = L[bl[L[x] - 1]];
        }

        if (!f)
            return;
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> q;

    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i];
        lc[x[i]] = y[i];
    }

    ++tot;
    lf[tot] = 1;

    for (int i = 1; i <= n; i++) {
        bl[i] = tot;

        if (lc[i] && i != n) {
            rf[tot] = i;
            tot++;
            lf[tot] = i + 1;

            if (lc[i] <= i) {
                add(tot, tot - 1);
                du[tot - 1]++;
            } else {
                add(tot - 1, tot);
                du[tot]++;
            }
        }
    }

    rf[tot] = n;
    queue<int> qq;

    for (int i = 1; i <= tot; i++) {
        if (!du[i])
            qq.push(i);
    }

    while (qq.size()) {
        int u = qq.front();
        qq.pop();
        solve(u);

        for (int i = head[u]; i; i = a[i].nex) {
            int v = a[i].to;

            if (!(--du[v]))
                qq.push(v);
        }
    }

    for (int i = 1; i <= q; i++) {
        cin >> qx >> qy;

        if (L[bl[qx]] <= qy && R[bl[qx]] >= qy)
            cout << "YES\n";
        else
            cout << "NO\n";
    }

    return 0;
}