[BOJ 14003 | C++] 가장 긴 증가하는 부분 수열 5 :: 세그먼트 트리, 역추적

• 문제 링크 : 14003번: 가장 긴 증가하는 부분 수열 5
• 문제 태그 : 이분 탐색, 가장 긴 증가하는 부분 수열:o(n log n)
• 관련 문제 : 2025.02.09 - [BOJ] - [BOJ 12015 | C++] 가장 긴 증가하는 부분 수열 2 :: 세그먼트 트리

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

 

풀이

12015번에서 역추적하는 부분만 추가했습니다. 

 

세그먼트 트리를 pair로 변경하여 기존의 dp값에 prv 배열의 값을 추가하여 관리하였습니다.

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

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, pair(0, -1));	// pair = dp, prv
	auto update = [&](int i, int x, int p) {
		i += sz;
		tree[i].first = x;
		tree[i].second = p;
		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;
		pair ans(0, -1);	// dp, prv

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

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

	int ans = query(0, n - 1).second;
	stack<int> stk;
	while (ans >= 0) {
		stk.push(input[ans]);
		ans = prv[ans];
	}

	cout << stk.size() << '\n';
	while (!stk.empty()) {
		cout << stk.top() << ' ';
		stk.pop();
	}
}