[BOJ 12015 | C++] 가장 긴 증가하는 부분 수열 2 :: 세그먼트 트리

• 문제 링크 : 12015번: 가장 긴 증가하는 부분 수열 2
• 문제 태그 : 이분 탐색, 가장 긴 증가하는 부분 수열:o(nlog n)

 

풀이

• input 배열 : 입력받은 수열 A를 저장합니다.
• dp[i] : 수열 A에서 i번째 원소를 마지막 원소로 가지는 LIS의 길이를 저장합니다.
• 세그먼트 트리 : Ai번째 리프노드에 dp[i]의 값을 이용하여 업데이트합니다. 주의할 점은 리프노드가 수열의 크기가 아니라 수열의 값이라는 것입니다. 
  •  예를 들어, 예제 입력 1을 이용하여 세그먼트 트리를 구성할 때, 트리의 리프노드는 0, 1, 2, 3, 4,5가 아닌 0부터 50(Ai의 최댓값)까지입니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1 << 30;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	vector input(n, 0);
	for (int i = 0;i < n;i++) cin >> input[i];

	// coordinate compression
	auto compress = [](int n, auto v) {
		vector buc(n, pair(0, 0));
		for (int i = 0;i < n;i++) {
			buc[i].first = v[i];
			buc[i].second = i;
		}
		sort(buc.begin(), buc.end());

		vector ans(n, 0);
		int cnt = 0;
		for (int l = 0, r = 0; l < n; l = r) {
			while (r < n && buc[l].first == buc[r].first) r++;
			
			for (int i = l;i < r;i++) {
				ans[buc[i].second] = cnt;
			}
			cnt++;
		}
		return ans;
	};

	// max segment tree
	int sz = 1;
	while (sz < n) sz *= 2;
	vector tree(sz * 2, 0);
	auto update = [&](int i, int x) {
		i += sz;
		tree[i] = x;
		while (i > 1) {
			i /= 2;
			tree[i] = max(tree[2 * i], tree[2 * i + 1]);
		}
	};

	auto query = [&](int l, int r) {
		l += sz;
		r += sz;
		int ans = 0;	// 구간에서 최댓값

		while (l <= r) {
			if (l % 2 == 1) {
				ans = max(tree[l], ans);
				l++;
			}
			if (r % 2 == 0) {
				ans = max(tree[r], ans);
				r--;
			}
			l /= 2;
			r /= 2;
		}
		return ans;
	};

	vector v = compress(n, input);
	vector dp(n, 0);
	for (int i = 0;i < n;i++) {
		dp[i] = query(0, v[i] - 1) + 1;
		update(v[i], dp[i]);
	}

	cout << query(0, n - 1) << '\n';
}