CF319E

ademik · 2023-07-15 10:15:35 · 题解

分析:

并查集 + 线段树。

首先，我们意识到两个区间能否到达是 一条单向边，且两个区间间的关系只有三种情况。

对于两个可以互达的区间，显然，我们可以将他们合并为 一个大区间，大区间的端点为 \min(x_1, x_2), \max(y_1, y_2)，我们可以用 并查集 来表示这种关系。

怎样判断两个区间是否有这样的关系？

考虑到每个区间的关系只与相对位置有关，我们先将所有点离散化。那么此时，最多的点的个数为 2 \times 10^5。我们完全可以利用 vector 存储每个点所在的区间。考虑到区间的长度一定单调递增，那么新增的区间一定不可能被其他区间所包含，那么此时，它与之前的区间要么可以互达，要么只能由其他区间到达它，要么毫无联系，因此，求与它能够互达的区间实际上是求它的两个端点处被多少区间经过。

再想到如果一个点一个点地打标记，时间复杂度过高。我们可以利用线段树，给一定的区间打标记，而不下传到每个子节点，使修改的时间复杂度达到 O(\log n)。

最终的询问即判断两个区间是否在同一个集合中 或者 两个集合是否互相包含。

Code：

using namespace std;
typedef long long i64;
const int N = 1e5 + 50;
int n, id[N << 2], idx, tot;
struct node {
    int op, x, y;
} a[N];
vector <int> g[N << 2];
int fa[N], c[N], d[N];
int _find(int x) {return fa[x] == x ? x : fa[x] = _find(fa[x]);}
void merge(int pos, int l, int r, int rt)
{
    if(g[rt].size()) {
        for(int i = 0; i < (int)g[rt].size(); i ++) {
            int x = _find(g[rt][i]), y = tot;
            fa[x] = y;
            c[y] = min(c[y], c[x]);
            d[y] = max(d[y], d[x]);
        }
        g[rt].clear();
        g[rt].push_back(tot);
    }
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(pos <= mid) merge(pos, l, mid, rt << 1);
    else merge(pos, mid + 1, r, rt << 1 | 1);
    return;
}
void insert(int x, int y, int l, int r, int rt)
{
    if(x == l && y == r) {
        g[rt].push_back(tot);
        return;
    }
    int mid = (l + r) >> 1;
    if(y <= mid) insert(x, y, l, mid, rt << 1);
    else if(x > mid) insert(x, y, mid + 1, r, rt << 1 | 1);
    else {
        insert(x, mid, l, mid, rt << 1);
        insert(mid + 1, y, mid + 1, r, rt << 1 | 1);
    }
    return;
}
int main() 
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >>n;
    for(int i = 1; i <= n; i ++) {
        cin >>a[i].op >>a[i].x >>a[i].y;
        if(a[i].op == 1) id[++ idx] = a[i].x, id[++ idx] = a[i].y;
    }
    sort(id + 1, id + 1 + idx); 
    idx = unique(id + 1, id + 1 + idx) - id - 1;
    for(int i = 1; i <= n; i ++) {
        if(a[i].op == 1) {
            a[i].x = lower_bound(id + 1, id + 1 + idx, a[i].x) - id;
            a[i].y = lower_bound(id + 1, id + 1 + idx, a[i].y) - id;
            tot ++;
            fa[tot] = tot;
            c[tot] = a[i].x;
            d[tot] = a[i].y;
            merge(a[i].x, 1, idx, 1);
            merge(a[i].y, 1, idx, 1);
            if(a[i].x + 1 <= a[i].y - 1) insert(a[i].x + 1, a[i].y - 1, 1, idx, 1);
        }
        else {
            int x = _find(a[i].x), y = _find(a[i].y);
            if(x == y || (c[y] < d[x] && d[y] > d[x]) || (c[y] < c[x] && d[y] > c[x])) cout <<"YES" <<endl;
            else cout <<"NO" <<endl;
        }
    }
    return 0;   
}