BOJ)1666 최대 증가 직사각형 집합

문제: icpc.me/1666

여러 직사각형이 주어졌을 때 이중 몇개의 직사각형을 골라서 집합을 만들것이다.

이때 집합의 조건은 집합의 임의의 두 원소를 선택했을 때 두 직사각형중 한 직사각형이 다른 한 직사각형보다 오른쪽 위에 있어야한다는 조건이다.

우선 각 원소를 왼쪽 아래 점의 x좌표 기준으로 스위핑하여 문제를 푸려고한다.

우리는 각 원소를 비교해나가며 쿼리를 처리하며 세그먼트 트리에 업데이트 할 것인데 이 때 비교는 왼쪽 아래 점과 하며 업데이트는 오른쪽 윗 점을 할것이다.

x좌표 기준으로 정렬을 했기 때문에 우리는 세그먼트 트리에 y좌표의 위치에 업데이트 할 것이다. 이때 좌표압축을 사용해 노드를 줄인다.

하지만 우리는 비교는 왼쪽 아래 점 기준으로 하며 정렬도 왼쪽 아래 점 기준으로 하지만 업데이트는 오른쪽 윗 점에 할 예정이기 때문에 

priority queue를 이용하여 매 쿼리마다 업데이트 할 점을 비교하여 알맞을 때 업데이트 시킬 것이다.

업데이트는 그 지점까지의 원소개수의 최댓값을 저장할 것이다.

따라서 우리는 현재 보고있는 왼쪽 아래점의 y좌표(좌표 압축에서 얻어온)보다 작은 값중 최댓값+1을 업데이트 시켜주면 된다.

이후 쿼리를 다 처리 해준 후 전체 범위에서 최댓값을 출력해주면 된다.

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#define MAX_N 100000
using namespace std;
typedef long long ll;
ll n, a, b, c, d, seg[8 * MAX_N], res;
vector<ll> ypos;
struct node {
    ll x1, y1, x2, y2;
};
struct element {
    ll x, y, z;
    bool operator<(const element &A)const {
        return x > A.x;
    }
};
node arr[MAX_N];
bool cmp(node x, node y) {
    return x.x1 < y.x1;
}
ll update(ll pos, ll val, ll node, ll x, ll y) {
    if (y < pos || pos < x)
        return seg[node];
    if (x == y)
        return seg[node] = max(val, seg[node]);
    ll mid = (x + y) >> 1;
    return seg[node] = max(update(pos, val, node * 2, x, mid), update(pos, val, node * 2 + 1, mid + 1, y));
}
ll query(ll lo, ll hi, ll node, ll x, ll y) {
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&y <= hi)
        return seg[node];
    ll mid = (x + y) >> 1;
    return max(query(lo, hi, node * 2, x, mid), query(lo, hi, node * 2 + 1, mid + 1, y));
}
ll make_y_index(ll pos) {
    return lower_bound(ypos.begin(), ypos.end(), pos) - ypos.begin();
}
int main() {
    scanf("%lld", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
        arr[i] = { a,b,c,d };
        ypos.push_back(b);
        ypos.push_back(d);
    }
    sort(arr, arr + n, cmp);
    sort(ypos.begin(), ypos.end());
    ypos.erase(unique(ypos.begin(), ypos.end()), ypos.end());
    const ll MAXY = ypos.size();
    priority_queue<element> pq;
    for (int i = 0; i < n; i++) {
        while (pq.size() && pq.top().x < arr[i].x1) {
            ll p = make_y_index(pq.top().y);
            update(p, pq.top().z, 1, 0, MAXY - 1);
            pq.pop();
        }
        ll p = make_y_index(arr[i].y1);
        ll q = query(0, p - 1, 1, 0, MAXY - 1);
        pq.push({ arr[i].x2,arr[i].y2,q + 1 });
    }
    while (pq.size()) {
        ll p = make_y_index(pq.top().y);
        update(p, pq.top().z, 1, 0, MAXY - 1 );
        pq.pop();
    }
    printf("%lld\n", seg[1] );
    return 0;
}