Boj 2995) Poklon

LIS-BinarySearch

백준 2995

설명

Interval 을 (x, y) 라고 생각하면 x 를 우선 오름차순으로 정렬하고 다음으로 y 를 내림차순으로 정렬하면 LIS 문제가 됨.

x 를 최고 우선순위로 오름차순으로 하면 먼저 LIS 배열에 들어가는 값은 x 가 작음. 그래서 이후에 x 가 다른 값이 이전 값의 Inteval 을 포함할 수 없어짐. 그래서 문제는 y 에 대한 LIS 문제가 됨.

y 가 내림차순이 아니면 일이 조금 복잡해짐. 예를들어 (2, 3), (2, 4), (2, 5) 이런식으로 올 때, 이전 Interval 이 이후를 포함해야하므로, (2, 5), (2, 4), (2, 3) 순이 되어야함. 이걸 하려면 insert 를 하거나 아니면 애초에 정렬을 내림차순으로 해 이런일이 없게하면 됨.

실제 값을 추적도 해야하는데, 최댓값 같은 제한이 없어서 조건만 만족하면 됨. LIS 배열 크기를 증가하기 위해서 무조건 그 이전 인덱스의 값이 존재하기 때문 임. 즉 index_map 에서 if 문 내에서 break 를 걸어도 되고 안걸어도 됨.

시간 복잡도

O(nLogN)

코드

struct Line { int x, y; };
Line lines[100001];
vector<Line> LIS;
vector<Line> ans;
unordered_map<int, vector<Line>> index_map;

int main()
{
	fastio;

	int n;
	cin >> n;
	
	for (int i = 0; i < n; i++)
		cin >> lines[i].x >> lines[i].y;
	
	sort(lines, lines + n, [](Line& lh, Line& rh) { return lh.x != rh.x ? lh.x < rh.x : lh.y > rh.y; });
	
	for (int i = 0; i < n; i++)
	{
		auto p = upper_bound(LIS.begin(), LIS.end(), lines[i]
			, [](const Line& a, const Line& b) { return a.y > b.y; });
		index_map[p - LIS.begin()].push_back(lines[i]);
		if (p == LIS.end()) 
			LIS.emplace_back(lines[i]);
		else *p = lines[i];
	}
	
	ans.resize(LIS.size());
	ans[LIS.size() - 1] = index_map[LIS.size()-1][0];
	for (int i = LIS.size()-2; i >= 0; i--)
	{
		for (auto& c : index_map[i])
		{
			if (ans[i + 1].x >= c.x && ans[i + 1].y <= c.y)
				ans[i] = c;
		}
	}
	cout << ans.size() << '\n';
	for_each(ans.begin(), ans.end(), [](const Line& a) { cout << a.x << " " << a.y << '\n'; });
}