题解：CF319E Ping-Pong

· · 题解

Happy New Year!

Solution

1

考虑这样的 subtask 如何做：给定的区间保证互不包含。此时很简单，直接把有交的区间用并查集合并，查询时看两个区间是否在同一连通块即可。

为何区间包含会困难。不妨记 D_a 被 D_b 所包含。在上面的 subtask 中，这种“可达性”是双向的，但此时 D_a \rightarrow D_b，而 D_b \nrightarrow D_a。发现这种包含和相交关系可能会很复杂。

2

也许能沿用 subtask 的做法，即使只是优化一点？考虑依旧把相交的区间用并查集合并起来，意义依旧是同一连通块的区间互相可达。

此时若我们把合并到一起的区间看成一个大的连续区间：

啊这就很好处理了哇。因为对于包含关系，那必然都是形如 D_a \rightarrow D_b 这样的行走方式了。因为路程中非形如 D_a \rightarrow D_b 的行走方式已经都被我们压入并查集的同一个连通块不予考虑了。

3

咋维护。这时候一直没用上的特殊性质“保证每次给出的区间长度单增”终于能用上了。

此时我们会把符合下述条件之一的大区间和新区间 [l,r] 合并：

原因很简单吧。同时，特殊性质告诉我们，只要 [L,R] 包含 [l,r]，则 [l,r] 必然和其中某个小区间相交，也即这俩区间可以合并。反证法，如果不存在，说明存在某一个小区间完全包含了 [l,r]，但因为长度单增，所以不可能。

那直接用线段树维护一下覆盖到 l 和 r 的区间有哪些就行了。

Code

复杂度就是单老哥，并查集懒得优化了，常数略大。

#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define fi first
#define se second
#define mkp make_pair

const int maxn = 1e5 + 5, maxm = 1e6 + 6;

int n, b[maxm], m;
pii D[maxn], Q[maxn]; int op[maxn], fa[maxn], d;

inline void ckmn(int &x, int v){ if(v < x) x = v; }
inline void ckmx(int &x, int v){ if(v > x) x = v; }

inline int fnd(int x){
    return fa[x] == x ? x : fa[x] = fnd(fa[x]);
}

#define ls (x << 1)
#define rs (x << 1 | 1)

vector<int> t[maxn << 2];

inline void updtr(int x, int l, int r, int L, int R, int id){
    if(L > R) return;
    if(l >= L and r <= R) return t[x].push_back(id), void();
    int mid = l + r >> 1;
    if(L <= mid) updtr(ls, l, mid, L, R, id);
    if(R > mid) updtr(rs, mid + 1, r, L, R, id);
}

vector<int> A;
inline void qryp(int x, int l, int r, int p){
    for(int v : t[x]) A.push_back(v); t[x].clear();
    if(l == r) return;
    int mid = l + r >> 1;
    if(p <= mid) qryp(ls, l, mid, p); else qryp(rs, mid + 1, r, p);
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL);

    cin >> n;
    rep(i, 1, n) cin >> op[i] >> Q[i].fi >> Q[i].se, fa[i] = i;
    rep(i, 1, n) if(op[i] == 1) b[++m] = Q[i].fi, b[++m] = Q[i].se;

    sort(b + 1, b + m + 1);
    m = unique(b + 1, b + m + 1) - b - 1;
    rep(i, 1, n) if(op[i] == 1) 
        Q[i].fi = lower_bound(b + 1, b + m + 1, Q[i].fi) - b,
        Q[i].se = lower_bound(b + 1, b + m + 1, Q[i].se) - b;

    rep(i, 1, n){
        if(op[i] == 1){
            A.clear(); qryp(1, 1, m, Q[i].fi), qryp(1, 1, m, Q[i].se);
            ++d;
            D[d].fi = Q[i].fi, D[d].se = Q[i].se;
            for(int x : A) 
                fa[x] = d, ckmn(D[d].fi, D[x].fi), ckmx(D[d].se, D[x].se);
            updtr(1, 1, m, D[d].fi + 1, D[d].se - 1, d);
        } else{
            int x = fnd(Q[i].fi), y = fnd(Q[i].se);
            if(x == y or (D[x].fi >= D[y].fi and D[x].se <= D[y].se)) cout << "YES" << '\n';
            else cout << "NO" << '\n';
        }
    }
    return 0;
}