「CF319E」Ping-Pong「线段树」「并查集」

hongzy · 2019-10-21 21:03:19 · 题解

题意

规定区间(a,b)到区间(c,d)有边当且仅当c<a<d或c<b<d。

起初区间集合为空。有n（n\leq 10^5）次操作，每次操作形如：

题解

考虑连边的两种情况：第一种是包含，小的向大的连边；第二种是相交不包含，连双向边。

注意到答案最后不会走超过1条单向边，我们先考虑双向边。

由于是双向边，我们可以用并查集维护连通块。那对于一个新区间，我们得考虑它和哪些区间连双向边。

可以使用线段树来做这件事。把区间拆放到\log个线段树结点上。加新区间连边就把左右端点对应线段树叶子结点到根到路径上所有放的路径都合并掉，然后把标记改成自己。题目给了一个每次加入一个最长区间的限制，这样就保证了新区间不会被包含。复杂度也是对的，每个区间分\log段，每段加入一次删除一次。

询问就判是同个并查集，或者是包含关系就YES，否则NO。注意一个连通块要维护L和R用于判包含。

时间复杂度O(n\alpha(n)\log n) （有误请指出

#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
struct node {
    int op, l, r;
} a[N];
int q, n, b[N * 2], f[N], L[N], R[N];
inline bool bel(int u, int l, int r) {
    return l < u && u < r;
}
int find(int u) {
    return u == f[u] ? u : f[u] = find(f[u]);
}
vector<int> vec[N << 2];
void solve(int u, int l, int r, int p, int cur) {
    if(vec[u].size()) {
        for(int i = 0; i < (int) vec[u].size(); i ++) {
            int v = vec[u][i]; v = find(v); f[v] = cur;
            L[cur] = min(L[cur], L[v]); R[cur] = max(R[cur], R[v]);
        }
        vec[u].clear();
        vec[u].push_back(cur);
    }
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(p <= mid) solve(u << 1, l, mid, p, cur);
    else solve(u << 1 | 1, mid + 1, r, p, cur);
}
void pushe(int u, int l, int r, int ql, int qr, int cur) {
    if(l == ql && r == qr) {
        vec[u].push_back(cur);
        return ;
    }
    int mid = (l + r) >> 1;
    if(qr <= mid) pushe(u << 1, l, mid, ql, qr, cur);
    else if(ql > mid) pushe(u << 1 | 1, mid + 1, r, ql, qr, cur);
    else {
        pushe(u << 1, l, mid, ql, mid, cur);
        pushe(u << 1 | 1, mid + 1, r, mid + 1, qr, cur);
    }
}
int main() {
    scanf("%d", &q);
    for(int i = 1; i <= q; i ++) {
        scanf("%d%d%d", &a[i].op, &a[i].l, &a[i].r);
        if(a[i].op == 1) {
            b[++ n] = a[i].l; b[++ n] = a[i].r;
        }
    }
    sort(b + 1, b + n + 1);
    n = unique(b + 1, b + n + 1) - b - 1;
    int c = 0;
    for(int i = 1; i <= q; i ++) {
        if(a[i].op == 1) {
            a[i].l = lower_bound(b + 1, b + n + 1, a[i].l) - b;
            a[i].r = lower_bound(b + 1, b + n + 1, a[i].r) - b;
            c ++; f[c] = c; L[c] = a[i].l; R[c] = a[i].r;
            solve(1, 1, n, a[i].l, c);
            solve(1, 1, n, a[i].r, c);
            if(a[i].l < a[i].r - 1) {
                pushe(1, 1, n, a[i].l + 1, a[i].r - 1, c);
            }
        }
        if(a[i].op == 2) {
            int u = find(a[i].l), v = find(a[i].r);
            bool tag = u == v || bel(L[u], L[v], R[v]) || bel(R[u], L[v], R[v]);
            puts(tag ? "YES" : "NO");
        }
    }
    return 0;
}