专栏文章

题解：CF319E Ping-Pong

ppldzy
CF319E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqkiger
此快照首次捕获于
2025/12/04 06:17
3 个月前
此快照最后确认于
2025/12/04 06:17
3 个月前
查看原文
Happy New Year!

Solution

1

考虑这样的 subtask 如何做：给定的区间保证互不包含。此时很简单，直接把有交的区间用并查集合并，查询时看两个区间是否在同一连通块即可。
为何区间包含会困难。不妨记 DaD_a 被 DbD_b 所包含。在上面的 subtask 中，这种“可达性”是双向的，但此时 Da→DbD_a \rightarrow D_b，而 Db↛DaD_b \nrightarrow D_a。发现这种包含和相交关系可能会很复杂。

2

也许能沿用 subtask 的做法，即使只是优化一点？考虑依旧把相交的区间用并查集合并起来，意义依旧是同一连通块的区间互相可达。
此时若我们把合并到一起的区间看成一个大的连续区间：
  • 这些新区间相互不可能相交；
  • 这些新区间可能存在包含关系。
啊这就很好处理了哇。因为对于包含关系，那必然都是形如 Da→DbD_a \rightarrow D_b 这样的行走方式了。因为路程中非形如 Da→DbD_a \rightarrow D_b 的行走方式已经都被我们压入并查集的同一个连通块不予考虑了。

3

咋维护。这时候一直没用上的特殊性质“保证每次给出的区间长度单增”终于能用上了。
此时我们会把符合下述条件之一的大区间和新区间 [l,r][l,r] 合并：
  • 大区间 [L,R][L,R] 和 [l,r][l,r] 完全不相交；
  • 大区间 [L,R][L,R] 完全包含 [l,r][l,r]。
原因很简单吧。同时，特殊性质告诉我们，只要 [L,R][L,R] 包含 [l,r][l,r]，则 [l,r][l,r] 必然和其中某个小区间相交，也即这俩区间可以合并。反证法，如果不存在，说明存在某一个小区间完全包含了 [l,r][l,r]，但因为长度单增，所以不可能。
那直接用线段树维护一下覆盖到 ll 和 rr 的区间有哪些就行了。

Code

复杂度就是单老哥，并查集懒得优化了，常数略大。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...