分治常见Trick——启发式分裂+中间相遇法：CF1181E2

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133323437

https://www.luogu.com.cn/problem/CF1181E2

首先E1，也就是分治应该很好想

考虑到E2，首先看到题目是二维平面，有很多种分割方法，所以我们可以考虑拆维。

拆完之后我们考虑枚举分界点。枚举分界点暴力遍历过大，于是自然而然的，我们可以考虑中间相遇法。

但如果优雅的维护对应的集合呢？朴素思路使用set。考虑这个过程中会分裂成两个区间，一个小，一个大。暴力分裂似乎不太可惜，但我们可以考虑分出小的，保留大的，也就是启发式分裂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 100010
//#define M
//#define mo
struct node {
	int l, r, id; 
	bool operator <(const node &A) const {
		if(l==A.l) return id<A.id; 
		return l<A.l; 
	}
}c[N][4];
int n, m, i, j, k, T;
set<node>s[4]; 
int lx, ly, rx, ry; 

int solve(set<node>L[4]) {
	int i, j, p, k; 
	if(L[0].size()<=1) return 1; 
	set<node>R[4]; 
	set<node>::iterator it[4], t; 
	int mx[4]; 
	for(i=0; i<4; ++i) 
		it[i]=L[i].begin(), mx[i]=it[i]->r, ++it[i], R[i].clear(); 
	for(i=1; i<L[0].size(); ++i) {
		for(j=0; j<4; ++j) {
			if(it[j]->l>=mx[j]) {
				for(t=L[j].begin(); t!=it[j]; ) {
					p=t->id; ++t;
					for(k=0; k<4; ++k) 
						R[k].insert(c[p][k]),  
						L[k].erase(c[p][k]); 
				}
				return solve(L)	&& solve(R); 
			}
			mx[j]=max(mx[j], (it[j]->r)); ++it[j]; 
		}
	}
	return 0; 
}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	n=read(); 
	for(i=1; i<=n; ++i) {
		lx=read(); ly=read(); rx=read(); ry=read(); 
		c[i][0]={lx, rx, i}; s[0].insert(c[i][0]); 
		c[i][1]={-rx, -lx, i}; s[1].insert(c[i][1]); 
		c[i][2]={ly, ry, i}; s[2].insert(c[i][2]); 
		c[i][3]={-ry, -ly, i}; s[3].insert(c[i][3]); 
//		printf("%d %d %d %d\n", (int)s[0].size(), s[1].size(), s[2].size(), s[3].size()); 

	}
//	printf("%d %d %d %d\n", s[0].size(), s[1].size(), s[2].size(), s[3].size()); 
	printf(solve(s) ? "YES\n" : "NO\n"); 
	return 0;
}