백준 알고리즘 12015번 : 가장 긴 증가하는 부분 수열 2

링크

https://www.acmicpc.net/problem/12015

sol1) LIS + lower_bound

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;

int32_t main() {
  fastio;
  int n; cin >> n;
  vector<int> table(n),ans;
  for(int i = 0; i < n; i++) cin >> table[i];
  for(int i = 0; i < n; i++){
    if(ans.empty() || ans.back() < table[i]) ans.push_back(table[i]);
    else *lower_bound(ans.begin(), ans.end(), table[i]) = table[i];
  }
  cout << ans.size() << "\n";
}

sol2) LIS with 세그먼트 트리

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;

using pii = pair<int, int>;

struct maxSegTree {
	int tree[1 << 21];
	int sz = 1 << 20;
	void construct() {
		for (int i = sz - 1; i > 0; i--) {
			tree[i] = max(tree[i << 1], tree[i << 1 | 1]);
		}
	}
  // 1 - indexed
	void update(int i, int val) {
		--i |= sz; tree[i] = val;
		while (i >>= 1) {
			tree[i] = max(tree[i << 1], tree[i << 1 | 1]);
		}
	}
  // [l, r]
	int query(int l, int r) {
		--l |= sz, --r |= sz;
		int ret = 0;
		while (l <= r) {
			if (l & 1) ret = max(ret, tree[l++]);
			if (~r & 1) ret = max(ret, tree[r--]);
			l >>= 1, r >>= 1;
		}
		return ret;
	}
} MaxST;

int32_t main() {
  fastio;
  int n; cin >> n;
  vector<pii> v(n);
  for(int i = 0; i < n; i++){
    cin >> v[i].first;
    v[i].second = i + 1;
  }
  sort(v.begin(), v.end(),[](pii a,pii b){
    if(a.first != b.first) return a.first < b.first;
    return a.second > b.second;
  });
  for(int i = 0; i < n; i++){
    int idx = v[i].second;
    int maxVal = 0;
    if(idx != 1) maxVal = MaxST.query(1, idx - 1);
    MaxST.update(idx, maxVal + 1);
  }
  cout << MaxST.tree[1] << "\n";
}