백준 2370 시장선거 포스터

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

상당히 까다로운 문제였다.

문제에서 포스터를 각각의 L 과 R 즉 포스터 칸에 대한 좌표 값 압축이 필요 했고 그 값에 대해서 최종 붙여진 포스터의 번호가 필요했다.

이유는 1,000,000,000 이라서 배열의 값으로 쓰긴 너무 값이 크다.

즉 순서대로 나온 포스터에 번호 idx 를 부여 하고 

segment Tree 로 업데이트 해나가면서 압축된 포스터의 칸에 대해서 최종적으로 붙은 포스터를 구분한다.

그 방법은 맨 마지막에 붙은 포스터는 index 의 숫자가 가장 큰값이 될것이다.

#include <stdio.h>
#include <iostream>
#include <memory.h>
 
 
 
using namespace std;
 
typedef long long ll;
const int MAX_N = 20001;
 
int N;
int TN = 1;
 
int tree[MAX_N * 4];
int sortbuf[MAX_N * 2];
int Sorted[MAX_N * 2];
 
 
 
struct pos {
 
    int l;
    int r;    
};
 
typedef struct pos Pos;
Pos Ori[MAX_N];
 
 
int Lower(int s, int e, int val) {
 
    int ret = 0;
    while (s <= e) {
 
        int mid = (s + e) / 2;
 
        if (Sorted[mid] >= val) {
            
            ret = mid;
            e = mid - 1;
        }
        else {
            s = mid + 1;
        }
    }
    return ret;
}
 
 
 
 
int tmp[MAX_N * 2];
void MergeSort(int l, int r, int arr[]) {
 
    if (l == r)
        return;
 
    int half = (l + r) / 2;
    int li = l, ri = half + 1;
    int idx = li;
 
    MergeSort(l, half, arr);
    MergeSort(half + 1, r, arr);
 
 
    while (li <= half && ri <= r) {
 
        if (arr[li] < arr[ri])
            tmp[idx++] = arr[li++];
        else
            tmp[idx++] = arr[ri++];
    }
 
 
    while (li <= half) tmp[idx++] = arr[li++];
    while (ri <= r) tmp[idx++] = arr[ri++];
 
    for (int i = l; i <= r; i++)
        arr[i] = tmp[i];
}
 
//@update 함수이지만 각각의 값을 업데이트 해보기 //
void  update(int ql, int qr, int idx, int l, int r, int val) {
 
    if (ql <= l && r <= qr) {
        tree[idx] = val;
        return;
    }
 
    if ( qr < l || r < ql)
        return;
    
    int mid = (l + r) / 2;
 
    update(ql, qr, idx * 2, l, mid, val);
    update(ql, qr, idx * 2 +1 , mid +1, r, val);
 
}
 
int query(int idx) {
    int maxRet = 0;
 
    int Nidx = TN + idx - 1;
    //maxRet = tree[Nidx];
    maxRet = tree[Nidx] > maxRet ? tree[Nidx] : maxRet;
 
 
    Nidx >>= 1;
 
    while (Nidx > 0) {
 
        maxRet = tree[Nidx] > maxRet ? tree[Nidx] : maxRet;
        Nidx >>= 1;
    }
 
    return maxRet;
}
 
 
 
int main()
{
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    freopen("input.txt", "r", stdin); setbuf(stdout, NULL);
 
    int l, r;
    int check[MAX_N];
    memset(check, 0, sizeof(check));
 
    
    //max 값에 대헌 tree 의 초기 index 값
 
 
    TN = 32768;
 
    /*
    const int NN = 20000;
    while (TN < NN) {
        //while (TN < TNN) {
        TN <<= 1;
    }
    cout << "TN value [" << NN << "] " << endl;
    */
 
    cin >> N;
    memset(Sorted, 0x3f, sizeof(Sorted));
 
 
    int Idx = 0;
 
    for (int i = 1; i <= N; i++) {
 
        cin >> Ori[i].l >> Ori[i].r;
 
        sortbuf[++Idx] = Ori[i].l;
        sortbuf[++Idx] = Ori[i].r;
 
    }
    
    MergeSort(1, 2 * N, sortbuf);
    Idx = 0;
    for (int i = 1; i <= N * 2; i++)
    {
        if (sortbuf[i] == 0) continue;
        if (i == 1  || sortbuf[i] != sortbuf[i - 1])
            Sorted[++Idx] = sortbuf[i];
    }
 
 
    for (int i = 1; i <= N; i++) {
        
        l = Lower(1, Idx, Ori[i].l);
        r = Lower(1, Idx, Ori[i].r);
 
        update(l, r, 1, 1, TN, i);
    }
 
    // query 로 각각 구간에 ..가장 최근에 붙인 포스터를 업데이트 한다 
    for (int i = 1; i <= Idx; i++) {
        check[i] = query(i);
    }
 
    MergeSort(1, Idx, check);
 
    int ans = 0;
    for (int i = 1; i <= Idx; i++) {
        if (check[i] == 0) continue;
 
        if (i == 1 || check[i] != check[i - 1])
            ans++;        
    }
    
    cout << ans << "\n";
 
    return 0;
}