BOJ 12011 - Splitting the field (세그트리)

https://www.acmicpc.net/problem/12011

작년 중순에 동아리에서 소개해줬던 문제.

 

<문제 설명>

최대 5만마리의 소들의 좌표가 주어질때, 이 소들을 하나의 펜스에 딱 맞도록 다 들어가도록 할때 그 영억의 넓이 big과 두 영역으로 펜스를 나눠 넣을때 두 영역의 합 small에 대해 big-small의 최소값을 구해라.

(좌표 범위 최대 1e9)

 

<풀이>

한 영역의 크기는 (ymax-ymn)*(xmax-xmn)이다.

 

펜스가 나눠지는 모양은 다음과 같이 네가지 경우 뿐이다.

1,2,3,4

 

1,2번의 경우, x좌표 기준으로 오름차순 정렬한 후 다음과 같이 구할 수 있다.

3,4번의 경우, y좌표 기준으로 오름차순 정렬한 후, 같은 방법으로 구할 수 있다.

 

 

구간[l,r] y값 최대, y값 최소, x값 최대, x값 최소를 세그트리에 기록해두면 area를 로그시간에 구할 수 있으므로 전체 시간복잡도는  O(nlogn)이다.

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll, ll> T; //xmx, xmn, ymx, ymn
const int MAX = 5e4 + 4;
const int SMAX = (1 << 17);

T seg[SMAX];
T ie = { 0,1e9,0,1e9 }; //항등원

void construct() {
	for (int i = SMAX/2 - 1; i >= 1; i--) {
		ll a, b, c, d, x, y, z, w;
		tie(a, b, c, d) = seg[i * 2];
		tie(x, y, z, w) = seg[i * 2 + 1];
		seg[i] = { max(a,x),min(b,y),max(c,z),min(d,w) };
	}
}
T val(int s, int e, int node, int ns, int ne) {
	if (e < ns || ne < s) return ie;
	if (s <= ns && ne <= e) return seg[node];
	int mid = (ns + ne) / 2;
	ll a, b, c, d, x, y, z, w;
	tie(a, b, c, d) = val(s, e, node * 2, ns, mid);
	tie(x, y, z, w) = val(s, e, node * 2 + 1, mid + 1, ne);
	return { max(a,x),min(b,y),max(c,z),min(d,w) };
}
T val(int s, int e) {
	return val(s, e, 1, 0, SMAX / 2 - 1);
}


int main() {
	FAST;
	ll n; cin >> n;
	P p[MAX];
	for (int i = 0; i < n; i++) 
		cin >> p[i].first >> p[i].second;
		
	sort(p, p + n, [](P p1, P p2) {
		return p1.first < p2.first;
		});

	fill(&seg[0], &seg[SMAX - 1], ie);
	for (int i = 0; i < n; i++)
		seg[SMAX / 2 + i] = { p[i].first, p[i].first, p[i].second, p[i].second };
	construct();

	ll a,b,c,d,big;
	tie(a, b, c, d) = val(0, n - 1);
	big = (a-b)*(c-d);
	
	ll small = 2e18;
	for (int i = 0; i < n-1; i++) {
		ll a, b, c, d, area1, area2;
			
		tie(a, b, c, d) = val(0, i);
		area1 = (a - b) * (c - d);
		
		tie(a, b, c, d) = val(i+1, n-1);
		area2 = (a - b) * (c - d);		
		
		small = min(small, area1+area2);
	}

	sort(p, p + n, [](P p1, P p2) {
		return p1.second < p2.second;
		});

	for (int i = 0; i < n; i++)
		seg[SMAX / 2 + i] = { p[i].first, p[i].first, p[i].second, p[i].second };
	construct();

	for (int i = 0; i < n - 1; i++) {
		ll a, b, c, d, area1, area2;
		
		tie(a, b, c, d) = val(0, i);
		area1 = (a - b) * (c - d);
				
		tie(a, b, c, d) = val(i + 1, n - 1);
		area2 = (a - b) * (c - d);		

		small = min(small, area1 + area2);
	}

	cout << big - small << '\n';
}

 

<생각>

더 빠른 코드를 보니 세그트리까지 사용하지않고 0번에서 시작하는 구간최대최소와 n-1번에서 시작하는 구간최대최소 배열만 있으면 O(n)에 풀 수 있다.