思路与算法

一个SCC内各区间的开并集必为一段开区间，用(L,R)表示。不同SCC的这些范围只能互不相交或包含；若发生交叉重叠，连接相交链就会使它们互通而成为同SCC。新区间(x,y)严格长于所有旧单个区间，所以只要x或y在某个旧SCC的开并集内，它便能走到该SCC，同时该SCC中覆盖此端点的旧短区间有另一端落在新区间内，故反向也可走，应立即合并。将所有操作的端点离线压缩，但按原顺序执行；每个活动SCC以左端点为线段树叶位置，叶内有序集合保存(右端点,代表元)，线段树存最大右端点。对x或y在“左端点<当前值”的前缀内寻找右端点>当前值的分量，反复移除并并入新代表元，最后插入合并后的包围区间。查询a到b：若并查集相同则YES；否则当且仅当原始区间a的任一端点严格落入b的SCC开并集。

正确性说明

SCC的区间并集连通，因为任何图边都要求两区间开重叠。不同SCC若范围交叉，沿各自覆盖交叉段的相交链会出现双向端点进入，从而互相可达，矛盾；因此SCC范围具有层叠结构，分量间单向边只朝包含自身的外层。新区间每条向旧SCC的边都因严格更长而有反向边，所报告的全部分量都应与新区间合并；沿这些分量向外层的可达目标也包含同一新区间端点，所以会被同一刺点查询报告，不遗漏经传递才加入的SCC。未报告的内部旧分量只有向外可达，不应误合并。对查询，端点落入目标并集给出直接进入目标SCC的边；反之从其他分量到目标只能沿包含方向上行，故最初原区间的某个端点也必严格位于目标并集。必须使用原始a端点，不能只用a的包围范围替代；相等边界不满足严格关系。

复杂度

压缩、集合和线段树初始化O(n log n)时间、O(n)空间。每个SCC活动记录只插入一次，合并时移除后不再插回旧代表元，全部刺点报告总数O(n)。每次查找、删除、插入及线段树更新O(log n)，总O(n log n)。并查集采用路径压缩而非按秩合并，强制以新点为代表元，所有find的总成本用O(n log n)摊还界计算，不声称仅凭路径压缩达到α(n)。总空间O(n)。

易错点

输入保证长度严格递增是算法关键，不是按左端点递增。所有包含比较都是严格小于；刚接触或边界相等不代表可走。端点是int32，但长度可达2^32-1，生成/校验时用更宽的差。SCC范围可以包含未并入的子分量，不能把范围内所有区间一律合并。相同包围范围的不同SCC可能共存，叶集合须保留唯一代表元。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Op {
    int type, a, b;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<Op> ops(n);
    vector<int> xs;
    for (auto &o : ops) {
        cin >> o.type >> o.a >> o.b;
        if (o.type == 1) {
            xs.push_back(o.a);
            xs.push_back(o.b);
        }
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    int K = 1;
    while (K < (int)xs.size())
        K *= 2;
    vector<long long> mx(2 * K, LLONG_MIN);
    vector<set<pair<int, int>>> at(xs.size());
    vector<int> par(n + 1), L(n + 1), R(n + 1), left(n + 1), right(n + 1);
    iota(par.begin(), par.end(), 0);
    function<int(int)> find = [&](int u) {
        int v = u;
        while (par[v] != v)
            v = par[v];
        while (par[u] != u) {
            int z = par[u];
            par[u] = v;
            u = z;
        }
        return v;
    };
    auto update = [&](int p) {
        int z = p + K;
        mx[z] = at[p].empty() ? LLONG_MIN : at[p].rbegin()->first;
        for (z /= 2; z; z /= 2)
            mx[z] = max(mx[z * 2], mx[z * 2 + 1]);
    };
    function<int(int, int, int, int, long long)> stab = [&](int z, int l, int r, int qr,
                                                            long long x) {
        if (l > qr || mx[z] <= x)
            return -1;
        if (l == r)
            return l;
        int m = (l + r) / 2;
        int p = stab(z * 2, l, m, qr, x);
        return p < 0 ? stab(z * 2 + 1, m + 1, r, qr, x) : p;
    };
    int count = 0;
    for (auto o : ops) {
        if (o.type == 1) {
            int u = ++count;
            left[u] = L[u] = o.a;
            right[u] = R[u] = o.b;
            for (int x : {o.a, o.b}) {
                int qr = lower_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
                while (qr >= 0) {
                    int pos = stab(1, 0, K - 1, qr, x);
                    if (pos < 0)
                        break;
                    auto z = *at[pos].rbegin();
                    int v = z.second;
                    at[pos].erase(z);
                    update(pos);
                    par[v] = u;
                    L[u] = min(L[u], L[v]);
                    R[u] = max(R[u], R[v]);
                }
            }
            int pos = lower_bound(xs.begin(), xs.end(), L[u]) - xs.begin();
            at[pos].insert({R[u], u});
            update(pos);
        } else {
            int a = o.a, b = find(o.b);
            bool ok = find(a) == b || (L[b] < left[a] && left[a] < R[b]) ||
                      (L[b] < right[a] && right[a] < R[b]);
            cout << (ok ? "YES" : "NO") << '\n';
        }
    }
}