题解

思路概述

• 题面允许我们询问三个位置的中位数。只要掌握“当前最小的两个值”和“当前最大的两个值”，就能用一问把第 $m$ 个数分类：用一个“偏大”的代表和一个“偏小”的代表与新位置组成查询，中位数小于现有的“低端”阈值说明新数更小；中位数大于“高端”阈值说明更大；否则新数落在中间（我们直接输出它的值）。
• 首先对前四个位置做四次询问，得到四个三元组的中位数。最小的中位数对应两个最小值所在的位置，最大的中位数对应两个最大值所在的位置。把它们分别记作 (i,j) 与 (k,l) 并记录对应的中位数 x、y，其中 x 是“低端哨兵”的值，y 是“高端哨兵”的值。
• 之后依次处理第 m (≥5) 个位置：询问 ask(i, k, m)。
  • 若结果小于 x，说明 a_m 比当前最小值还小，于是原来的“低端第二小”j 已经确定，它的值就是旧的 x，输出后用m替换 j。
  • 若结果等于 x，则原来的 i 可以确定，其值即 x。随后重新用 ask(i, j, m)（此时 i 还是旧的哨兵）得到新的 x，并把 i 更新为 m 充当新的“低端代表”。
  • 同理，若结果大于 y 或等于 y，就处理“高端”两位 (k,l)。
  • 如果落在 x 与 y 之间，则直接输出当前位置的值（因为三数中位数就是它本身）。
• 这样每加入一个新位置都会确定并输出至少一个旧位置的数值；当新数位于两哨兵之间时，我们也能立即输出它本身，因此总询问次数为 $O(n)$。

实现细节

• answer(x, v) 在确定下标 x 的真实值后立即调用；每个下标最多输出一次，符合题面限制。
• 维护的四个位置 (i,j,k,l) 始终互不相同。由于每次只做常数次 ask 操作，整体询问次数与常数因子都较小。
• 当 N < 4 时无法构造这样的哨兵，题解中直接返回，此时交互库不会要求输出具体答案。

复杂度

仅做常数次预处理询问，再对每个后续位置执行常数次 ask，故总询问次数与时间复杂度均为 $O(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;
}