가장 큰 증가하는 부분 수열 2 (백준 27989)

안녕하세요. 오늘은 가장 큰 증가하는 부분수열을 찾을 거예요.

문제

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

아이디어

이 문제는 세그먼트 트리로 풀 수 있습니다.
i<j && A[i]<A[j]인 모든 값들에 대해서 탐색을 해야하므로 두가지 방법이 있습니다.
1. 인덱스 기준으로 정렬 (이미 되어있지만) 후 1부터 N까지 탐색하면서 값 기준으로 세그트리
2. 값 기준으로 정렬 후 1부터 N까지 탐색하면서 인덱스 기준으로 세그트리

구체적으로 1번 방법은
1. 인덱스 1부터 N까지 순서대로 탐색
2. 자신보다 작은 수가 있는 곳중에서 dp값의 최댓값을 가져오기
3. 그 값 + 자신의 값이 자신의 dp값
4. 세그트리 갱신
2번은
1. 정렬
2. 인덱스 1부터 N까지 순서대로 탐색
3. 자신보다 작은 인덱스가 있는 곳중에서 dp값의 최댓값을 가져오기
4. 그 값 + 자신의 값이 자신의 dp값
5. 세그트리 갱신

하지만 1번 방법은 수를 기준으로 세그트리를 해야한는데 수의 범위 때문에 값 압축을 해야해서 2번으로 풀겠습니다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

ll tree[1212121] = { 0 };
ll MAX(ll s, ll e, ll node, ll l, ll r)
{
    if (e < l || r < s) return 0;
    if (l <= s && e <= r) return tree[node];
    ll mid = (s + e) / 2;
    return max(MAX(s, mid, node * 2, l, r), MAX(mid + 1, e, node * 2 + 1, l, r));
}
void change(ll s, ll e, ll node, ll idx, ll num)
{
    if (e < idx || idx < s) return;
    tree[node] = max(tree[node], num);
    if (s == e) return;
    ll mid = (s + e) / 2;
    change(s, mid, node * 2, idx, num);
    change(mid + 1, e, node * 2 + 1, idx, num);
}

bool cmp(pair <ll, ll> A, pair <ll, ll> B) //값을 오룸차순, 값이 같으면 인덱스가 큰것이 먼저
{
    if (A.first != B.first) return A.first < B.first;
    return A.second > B.second;
}


int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    vector <pair <ll, ll> > v;
    ll N, i, x, ans = 0;

    cin >> N;
    for (i = 1; i <= N; i++)
    {
        cin >> x;
        v.push_back({ x,i });
    }
    sort(v.begin(), v.end(), cmp);

    for (i = 0; i < N; i++)
    {
        ll num = v[i].first, idx = v[i].second;
        ll Value = MAX(1, N, 1, 1, idx - 1) + num;
        ans = max(ans, Value);
        change(1, N, 1, idx, Value);
    }

    cout << ans;
}

감사합니다.