백준 12015번 가장 긴 증가하는 부분 수열2[C++]

1. 문제 풀이

 세그먼트 트리 자료구조를 사용해서 문제를 풀었습니다. 배열 정보를 입력 받아 { x, i }와 같은 pair 타입으로 배열에 저장합니다. x는 배열의 값이고, i는 x의 index입니다. 이를 오름차순으로 정렬합니다. 이 때, x의 값이 같을 때에는 i가 큰 순서가 먼저 오게 custom_sort가 필요합니다. 그 이유는 중복된 값을 수열의 길이에 추가하는 것을 방지하기 위함입니다. 다음 배열의 가장 작은 값부터 순회를 시작합니다. [ 0, i ] 범위에서 LIS의 최대 길이를 구한 다음, +1한 값으로 세그먼트 트리를 갱신해줍니다. 이를 모두 완료했다면 세그먼트 트리의 루트 값이 입력으로 주어진 배열에서 가장 긴 증가하는 부분 수열이 됩니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n;
int tree[2'000'005];
pi a[1'000'005];

int mxq(int l, int r){
  int ret{};
  for(l += n, r += n; l < r; l>>=1, r>>=1){
    if(l&1) ret = max(ret, tree[l++]);
    if(r&1) ret = max(ret, tree[--r]);
  }
  return ret;
}

void update(int p, int val){
  p += n;
  tree[p] = val;
  for(int i = p; i > 1; i >>= 1) tree[i>>1] = max(tree[i], tree[i^1]);
}

bool cmp(const pi &a, const pi &b){
  if(a.X == b.X) return a.Y > b.Y;
  return a.X < b.X;
}
int main() {
  fastio(nullptr, false);
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> a[i].X;
    a[i].Y = i;
  }
  sort(a, a+n, cmp);
  for(int i = 0; i < n; i++){
    int mx = mxq(0, a[i].Y) + 1;
    update(a[i].Y, mx);
  }
  cout << tree[1];
}

 

3. 제출 결과