题解：P12180 DerrickLo's City (UBC002C)

可爱大黄兔 · 2025-04-13 19:19:09 · 题解

题意

给定一个图，对于每个询问，判断是否存在一个点 p 使得对于 x \in [l,r]，x_i 至 p 不经过 x_j。

思路

我们很容易想到并查集，对于输入的每条边，将编号大的边合并给编号小的边，再用 zkw 线段树维护并查集编号最大值与最小值。每次询问判断两个最值其中一个是否不在 l,r 之间即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;
const int MAXN = 1e5 + 5;

int p[MAXN];

struct NODE {
    vector<int> mi, ma;
    int n;

    NODE(int size, int *arr) {
        n = 1;
        while (n < size)
            n <<= 1;
        mi.resize(2 * n, INT_MAX);
        ma.resize(2 * n, INT_MIN);
        for (int i = 0; i < size; i++) {
            mi[i + n] = arr[i + 1];
            ma[i + n] = arr[i + 1];
        }
        for (int i = n - 1; i > 0; i--) {
            mi[i] = min(mi[2 * i], mi[2 * i + 1]);
            ma[i] = max(ma[2 * i], ma[2 * i + 1]);
        }
    }

    PII query(int l, int r) {
        l--;
        r--;
        int rmi = INT_MAX;
        int rma = INT_MIN;
        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l % 2 == 1) {
                rmi = min(rmi, mi[l]);
                rma = max(rma, ma[l]);
                l++;
            }
            if (r % 2 == 0) {
                rmi = min(rmi, mi[r]);
                rma = max(rma, ma[r]);
                r--;
            }
        }
        return {rmi, rma};
    }
};
int n, q;
//int pma[200010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        p[i] = 0;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        if (a < b) {
            if (p[b] == 0 || p[b] > a)
                p[b] = a;
        } else {
            if (p[a] == 0 || p[a] > b)
                p[a] = b;
        }
    }
    NODE st_min(n, p);
    vector<int> pma(MAXN);
    for (int i = 1; i <= n; i++)
        pma[i] = p[i];
    NODE st_max(n, pma.data());
    while (q--) {
        int l, r;
        cin >> l >> r;
        auto [mip, map] = st_min.query(l, r);
        if (map < l || mip > r) {
            cout << "Yes\n";
            continue;
        }
        int cntp = 0;
        int flag = -1;
        for (int i = l; i <= r; i++) {
            if (p[i] >= l && p[i] <= r) {
                cntp++;
                flag = p[i];
            }
        }
        if (cntp == 0) {
            cout << "Yes\n";
            continue;
        }
        bool valid = true;
        int p1 = flag;
        for (int i = l; i <= r; i++) {
            if (i == p1)
                continue;
            if (p[i] != p1 && (p[i] < l || p[i] > r))
                continue;
            valid = false;
            break;
        }
        if (valid && (p[p1] < l || p[p1] > r)) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

    return 0;
}