C. Day at the Beach

RMQ, Mapping

출처: Codeforces C. Day at the Beach

sol)

데이터의 개수는 10만개 그런데 각각의 값은 10^9

따라서 수를 mapping한다. 그 후 세그먼트 트리를 이용

rmq에는 index의 최소값을 유지한다.

ex) 인풋이 1, 2, 2면 T[2+h] = 1이다.

이렇게 업데이트를 해주고 맨 뒤부터 본다.

쿼리는 '나보다 인덱스가 작으면서 큰 숫자가 있냐?'

만약 있다면  그 인덱스를 next라 하고 지금 인덱스부터

next까지 값을 살펴본다. 더 앞으로 가야하는 경우가 있다.

ex)

1 2 3 4 4 4 2 3

맨뒤의 3부터 시작하면 빨간색의 4가 걸린다.

하지만 무조건 빨간색 인덱스로 옮기면 안된다.

왜냐하면 2는 3보다 크기때문이다. 따라서 2도 조사를 

해줘야 하기 때문에 next까지 감소하면서 하나씩 본다.

이게 싫으면 rmq에 인덱스 최대값을 유지하는 녀석도 

필요할듯하다..

[-] Collapse

#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<map>
#include<set>
using namespace std;
int castle[100002];
int sorted[100002];
int T[4 * 100001];
map<int, int> mm;
int ans = 0;
int h = 1;
void update(int idx, int v){
    while (idx >= 1){
        T[idx]  = min(v, T[idx]);
        idx >>= 1;
    }
}
void update2(int idx, int v){
    while (idx >= 1){
        T[idx] = v;
        idx >>= 1;
    }
}
int query(int l, int r, int nth){
    int v = nth;
    while (l <= r){
        if (l & 1) v = min(T[l], v);
        if (!(r & 1)) v = min(T[r], v);
        l = (l + 1) >> 1;
        r = (r - 1) >> 1;
    }
    return v;
}
int main(){
    freopen("input.txt", "r", stdin);
    int n; scanf("%d", &n);
    for (int i = 0; i < 4 * 100001; i++) T[i] = 100001;
    for (int i = 0; i < n; i++) {
        scanf("%d", &castle[i]);
        sorted[i] = castle[i];
    }
    sort(sorted, sorted + n);
    for (int i = 0; i < n; i++){
        mm[sorted[i]] = i+1;
    }
    while (h < 100001) h <<= 1;
    for (int i = 0; i < n; i++){
        update(mm[castle[i]] + h, i);
    }
    for (int i = n-1; i >= 0;){
        int next = query(mm[castle[i]] + 1 + h, 100001 + h, i);
        if (next == i){
            ans++;
            i--;
        }
        else{
            for (int k = i-1; k >= next; k--){
                next = min(next, query(mm[castle[k]] + 1 + h, 100001 + h, k));
            }
            ans++;
            i = next - 1;
        }
    }
    printf("%d", ans);
    return 0;
}