UVA10131 Is Bigger Smarter?

LIS, Segment Tree

출처: UVA UVA10131 Is Bigger Smarter?

Sol)
 구간 트리를 이용한 LIS찾기 문제 첫 번째 값이 작으면 먼저오게
같으면 두 번째 값이 작으면 먼저오도록 소팅을 한다.
2번째 값과 구간 트리를 이용하여 dp테이블을 체우고
(i번째 원소까지를 이용하여 만들 수 있는 최대길이)
마지막에 역추적을 한다. 최대 dp[x]값을 찾고 i = x부터 1씩 감소시키며
x인덱스에 부모가 될 수 있는 녀석을 찾는다.
dp[x] - 1 == dp[i] 이 때 i번째 원소가 x번째 원소 앞에 올 수 있는지 검사한다.


[-] Collapse

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

int n, h = 1;
int T[4 *10002];
int dp[10000];

vector <pair<pair<int, int>, int> > ele;
void update(int idx, int v){
    while (idx >= 1){
        T[idx] = max(T[idx], v);
        idx >>= 1;
    }
}
int query(int l, int r){
    int ans = 0;
    while (l <= r){
        if (l & 1) ans = max(ans, T[l]);
        if (!(r & 1)) ans = max(ans, T[r]);
        l = (l + 1) >> 1;
        r = (r - 1) >> 1;
    }
    return ans;
}
int main(){
    freopen("input.txt", "r", stdin);
    memset(dp, 0, sizeof(dp));
    memset(T, 0, sizeof(T));
    int w, s;
    while (scanf("%d %d", &w, &s) != EOF){
        ele.push_back(make_pair(make_pair(w, s), ++n));
    }
    sort(ele.begin(), ele.end());
    while (h < 10000 + 1) h <<= 1;
    int mx = 0;
    for (int i = 0; i < n; i++){
        update(ele[i].first.second + h, 1);
        dp[i] = max(dp[i], 1);
        int v = query(ele[i].first.second + 1 + h, 10000 + h);
        if (dp[i] < v + 1){
            dp[i] = v + 1;
            update(ele[i].first.second + h, dp[i]);
        }
    }
    int ans = 0, idx = 0;
    for (int i = 0; i < n; i++){
        if (ans < dp[i]){
            ans = dp[i];
            idx = i;
        }
    }
    vector<int> vec; vec.push_back(ele[idx].second);
    int com_w = ele[idx].first.first;
    int com_s = ele[idx].first.second;
    int com_dp = dp[idx];
    for (int i = idx; i >= 0; i--){
        if (com_dp - 1 == dp[i]){
            if (ele[i].first.first < com_w && ele[i].first.second > com_s){
                com_w = ele[i].first.first;
                com_s = ele[i].first.second;
                com_dp = dp[i];
                vec.push_back(ele[i].second);
            }
        }
    }
    printf("%d\n", vec.size());
    for (int i = vec.size() - 1; i >= 0; i--)
        printf("%d\n", vec[i]);
    return 0;
}