BOJ 12015 - 가장 긴 증가하는 부분수열2 (segtree)

라이님 블로그에서 공부했음을 밝힘니다.

 

구간 최대값을 저장하는 세그먼트트리를 마련해 두자.

 

값을 입력받을 땐, {원소값, 인덱스} pair로 p배열을 만들고, 원소값 순 인덱스 역순으로 정렬해 준다.

 

p배열을 순서대로 방문하면서 세그트리를 업데이트 해준다. 마지막에 루트에 남은 값이 LIS길이가 된다.

 

 

#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;

int arr[1 << 21];

void update(int i, int v) {
	i += (1 << 20);
	arr[i] = v;
	while (i > 1) {
		i /= 2;
		arr[i] = max(arr[i * 2], arr[i * 2 + 1]);
	}
}

int val(int L, int R, int nodeNum, int nodeL, int nodeR) {
	if (R < nodeL || nodeR < L) return 0;
	if (L <= nodeL && nodeR <= R) return arr[nodeNum];
	int mid = (nodeL + nodeR) / 2;
	return max(val(L, R, nodeNum * 2, nodeL, mid), val(L, R, nodeNum * 2 + 1, mid + 1, nodeR));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n; cin >> n;

	pair<int, int> p[1000001];
	for (int i = 0,a; i < n; i++) {
		cin >> a;
		p[i] = { a,i };
	}
	sort(p, p + n, [](pair<int, int> p, pair<int, int> q) {
		if (p.first != q.first) return p.first < q.first;
		return p.second > q.second;
	});

	for (int i = 0; i < n; i++) {
		int temp = val(0, p[i].second, 1, 0, (1 << 20) - 1) + 1;
		update(p[i].second, temp);
	}
	cout << arr[1] << '\n';
}