题解 gym102900J 【Octasection】

代码：

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <cstdio>

using namespace std;

typedef struct Rectangle_tag {
	int x1;
	int x2;
	int y1;
	int y2;
	Rectangle_tag(int x1_, int x2_, int y1_, int y2_){
		x1 = x1_;
		x2 = x2_;
		y1 = y1_;
		y2 = y2_;
	}
} Rectangle;

int cnt1 = 0, cnt2 = 0, cnt3 = 0;
int lsh1[100007], lsh2[100007], lsh3[100007];

namespace SecondD {
	typedef struct {
		int l;
		int r;
		int chkmaxl;
		int chkminr;
		int minl;
		int maxl;
		int minr;
		int maxr;
		pair<int, int> pr1;
		pair<int, int> pr2;
		pair<int, int> pr3;
	} SegmentTreeNode;

	typedef struct StackNode_tag {
		int tm;
		int pos;
		SegmentTreeNode info;
		StackNode_tag(int tm_, int pos_, SegmentTreeNode info_){
			tm = tm_;
			pos = pos_;
			info = info_;
		}
	} StackNode;

	int top = 0, tm;
	SegmentTreeNode tree[400007];
	stack<StackNode> s;

	inline void update(int x){
		int ls = x * 2, rs = x * 2 + 1;
		tree[x].minl = min(tree[ls].minl, tree[rs].minl);
		tree[x].maxl = max(tree[ls].maxl, tree[rs].maxl);
		tree[x].minr = min(tree[ls].minr, tree[rs].minr);
		tree[x].maxr = max(tree[ls].maxr, tree[rs].maxr);
		tree[x].pr1 = min(tree[ls].pr1, tree[rs].pr1);
		tree[x].pr2 = max(tree[ls].pr2, tree[rs].pr2);
		tree[x].pr3 = max(tree[ls].pr3, tree[rs].pr3);
	}

	void build(int x, int l, int r){
		tree[x].l = l;
		tree[x].r = r;
		tree[x].chkmaxl = 0;
		tree[x].chkminr = 0x7fffffff;
		if (l == r){
			tree[x].minl = tree[x].maxl = 0;
			tree[x].minr = tree[x].maxr = cnt3;
			tree[x].pr1 = make_pair(0, l);
			tree[x].pr2 = tree[x].pr3 = make_pair(cnt3, l);
			return;
		}
		int mid = (l + r) >> 1;
		build(x * 2, l, mid);
		build(x * 2 + 1, mid + 1, r);
		update(x);
	}

	inline void push(int x){
		s.push(StackNode(tm, x, tree[x]));
	}
	
	inline bool check(int x){
		return tree[x].chkmaxl != 0 || tree[x].chkminr != 0x7fffffff;
	}

	inline void push_chkmaxl(int x, int k){
		tree[x].chkmaxl = tree[x].minl = tree[x].maxl = tree[x].pr1.first = k;
		tree[x].pr3 = make_pair(tree[x].pr2.first - k, tree[x].pr2.second);
	}

	inline void push_chkminr(int x, int k){
		tree[x].chkminr = tree[x].minr = tree[x].maxr = tree[x].pr2.first = k;
		tree[x].pr3 = make_pair(k - tree[x].pr1.first, tree[x].pr1.second);
	}

	inline void pushdown(int x){
		int ls = x * 2, rs = x * 2 + 1;
		if (tree[x].chkmaxl != 0){
			push_chkmaxl(ls, tree[x].chkmaxl);
			push_chkmaxl(rs, tree[x].chkmaxl);
			tree[x].chkmaxl = 0;
		}
		if (tree[x].chkminr != 0x7fffffff){
			push_chkminr(ls, tree[x].chkminr);
			push_chkminr(rs, tree[x].chkminr);
			tree[x].chkminr = 0x7fffffff;
		}
	}

	void chkmaxl(int x, int l, int r, int k){
		if (tree[x].minl >= k) return;
		push(x);
		if (l <= tree[x].l && tree[x].r <= r && tree[x].maxl < k){
			push_chkmaxl(x, k);
			return;
		}
		int mid = (tree[x].l + tree[x].r) >> 1;
		if (check(x)){
			push(x * 2);
			push(x * 2 + 1);
			pushdown(x);
		}
		if (l <= mid) chkmaxl(x * 2, l, r, k);
		if (r > mid) chkmaxl(x * 2 + 1, l, r, k);
		update(x);
	}

	void chkminr(int x, int l, int r, int k){
		if (tree[x].maxr <= k) return;
		push(x);
		if (l <= tree[x].l && tree[x].r <= r && tree[x].minr > k){
			push_chkminr(x, k);
			return;
		}
		int mid = (tree[x].l + tree[x].r) >> 1;
		if (check(x)){
			push(x * 2);
			push(x * 2 + 1);
			pushdown(x);
		}
		if (l <= mid) chkminr(x * 2, l, r, k);
		if (r > mid) chkminr(x * 2 + 1, l, r, k);
		update(x);
	}

	int getl(int x, int pos){
		if (tree[x].l == tree[x].r) return tree[x].minl;
		pushdown(x);
		if (pos <= ((tree[x].l + tree[x].r) >> 1)) return getl(x * 2, pos);
		return getl(x * 2 + 1, pos);
	}

	inline bool rollback(){
		if (s.empty()) return false;
		StackNode cur = s.top();
		if (cur.tm != tm) return false;
		s.pop();
		tree[cur.pos] = cur.info;
		return true;
	}
}

namespace FirstD {
	typedef struct {
		int l;
		int r;
		vector<Rectangle> v;
	} Node;

	Node tree[400007];

	void build(int x, int l, int r){
		tree[x].l = l;
		tree[x].r = r;
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(x * 2, l, mid);
		build(x * 2 + 1, mid + 1, r);
	}

	void insert(int x, int l, int r, Rectangle rec){
		if (l <= tree[x].l && tree[x].r <= r){
			tree[x].v.push_back(rec);
			return;
		}
		int mid = (tree[x].l + tree[x].r) >> 1;
		if (l <= mid) insert(x * 2, l, r, rec);
		if (r > mid) insert(x * 2 + 1, l, r, rec);
	}

	void dfs(int x){
		SecondD::tm++;
		for (register Rectangle i : tree[x].v){
			if (i.x1 > 1){
				SecondD::chkmaxl(1, 1, i.x1 - 1, i.y1);
				SecondD::chkminr(1, 1, i.x1 - 1, i.y2);
			}
			if (i.x2 < cnt2){
				SecondD::chkmaxl(1, i.x2 + 1, cnt2, i.y1);
				SecondD::chkminr(1, i.x2 + 1, cnt2, i.y2);
			}
		}
		if (tree[x].l == tree[x].r){
			if (SecondD::tree[1].pr3.first >= 0){
				cout << "YES" << endl;
				cout << lsh1[tree[x].l] << " " << lsh2[SecondD::tree[1].pr3.second] << " " << lsh3[SecondD::getl(1, SecondD::tree[1].pr3.second)];
				exit(0);
			}
		} else {
			dfs(x * 2);
			dfs(x * 2 + 1);
		}
		while (SecondD::rollback()) ;
		SecondD::tm--;
	}
}

int l1[100007], r1[100007], l2[100007], r2[100007], l3[100007], r3[100007];

int main(){
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		scanf("%d %d %d %d %d %d", &l1[i], &r1[i], &l2[i], &r2[i], &l3[i], &r3[i]);
		lsh1[++cnt1] = l1[i];
		lsh2[++cnt2] = l2[i];
		lsh3[++cnt3] = l3[i];
	}
	sort(lsh1 + 1, lsh1 + cnt1 + 1);
	cnt1 = unique(lsh1 + 1, lsh1 + cnt1 + 1) - lsh1 - 1;
	sort(lsh2 + 1, lsh2 + cnt2 + 1);
	cnt2 = unique(lsh2 + 1, lsh2 + cnt2 + 1) - lsh2 - 1;
	sort(lsh3 + 1, lsh3 + cnt3 + 1);
	cnt3 = unique(lsh3 + 1, lsh3 + cnt3 + 1) - lsh3 - 1;
	for (int i = 1; i <= n; i++){
		l1[i] = lower_bound(lsh1 + 1, lsh1 + cnt1 + 1, l1[i]) - lsh1;
		r1[i] = upper_bound(lsh1 + 1, lsh1 + cnt1 + 1, r1[i]) - lsh1 - 1;
		l2[i] = lower_bound(lsh2 + 1, lsh2 + cnt2 + 1, l2[i]) - lsh2;
		r2[i] = upper_bound(lsh2 + 1, lsh2 + cnt2 + 1, r2[i]) - lsh2 - 1;
		l3[i] = lower_bound(lsh3 + 1, lsh3 + cnt3 + 1, l3[i]) - lsh3;
		r3[i] = upper_bound(lsh3 + 1, lsh3 + cnt3 + 1, r3[i]) - lsh3 - 1;
	}
	FirstD::build(1, 1, cnt1);
	for (register int i = 1; i <= n; i++){
		Rectangle rec(l2[i], r2[i], l3[i], r3[i]);
		if (l1[i] > 1) FirstD::insert(1, 1, l1[i] - 1, rec);
		if (r1[i] < cnt1) FirstD::insert(1, r1[i] + 1, cnt1, rec);
	}
	SecondD::build(1, 1, cnt2);
	FirstD::dfs(1);
	cout << "NO";
	return 0;
}