[12015] 가장 긴 증가하는 부분수열2

• 입력: 수열의 크기N(1 ≤ N ≤ 1,000,000), 수열을 나타내는 정수 Ai (1 ≤ Ai ≤ 1,000,000)
• 출력: 가장 긴 증가하는 부분 수열의 길이를 출력
• 실패한 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <cmath> #include <vector> #include <algorithm> using namespace std; int max(vector<int>, int, int, int, int, int); void update(vector<int>&, int, int, int, int, int); int main() { int N; scanf("%d", &N); vector<pair<int, int> > arr(N); for (int i = 0; i < N; i++) { scanf("%d", &arr[i].first); arr[i].second = i; } sort(arr.begin(), arr.end()); int h = (int)ceil(log2(N)); vector<int> tree(1 << (h + 1), 0); int maxLength; for (int i = 0; i < N; i++) { maxLength = max(tree, 1, 0, arr[i].second, 0, N - 1); if (i != 0 && arr[i - 1].first == arr[i].first) update(tree, 1, 0, N - 1, arr[i].second, maxLength); else update(tree, 1, 0, N - 1, arr[i].second, maxLength + 1); } printf("%d\n", tree[1]); return 0; } int max(vector<int> tree, int node, int left, int right, int start, int end) { if (left > end || right < start) return 0; if (left <= start && end <= right) return tree[node]; int a = max(tree, node * 2, left, right, start, (start + end) / 2); int b = max(tree, node * 2, left, right, (start + end) / 2 + 1, end); return (a > b ? a : b); } void update(vector<int>& tree, int node, int start, int end, int index, int key) { if (index < start || index > end) return; tree[node] = (tree[node] > key ? tree[node] : key); if (start != end) { update(tree, node * 2, start, (start + end) / 2, index, key); update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, key); } }

세그먼트 트리를 이용하여 구현하였지만 시간초과가 났다. 트리에 가장 긴 부분수열의 길이를 기록한다.

• 성공한 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <cmath> #include <vector> #include <algorithm> using namespace std; int main() { int N; scanf("%d", &N); vector<int> arr(N); for (int i = 0; i < N; i++) scanf("%d", &arr[i]); vector<int> lis; lis.push_back(-1); for (int i = 0; i < N; i++) { if (lis.back() < arr[i]) { lis.push_back(arr[i]); } else { auto it = lower_bound(lis.begin(), lis.end(), arr[i]); *it = arr[i]; } } printf("%d\n", lis.size() - 1); return 0; }

세그먼트 트리가 아닌, 그냥 vector를 이용하여 구현하였다. lower_bound 함수를 사용했기 때문에 O(NlogN)일 것이라고 추정된다.

• C++ 참고: auto http://yejin0730.tistory.com/40 / lower_bound http://yejin0730.tistory.com/41
• 문제참고: https://www.acmicpc.net/problem/12015
• 소스코드 참고: http://jason9319.tistory.com/113 / http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220791986409