BOJ)2370 시장 선거 포스터

문제:icpc.me/2370

포스터를 붙이는 순서가 주어질 때 보이는 포스터의 수를 출력하는 문제이다.

포스터의 모든 x좌표와 y좌표를 좌표압축 한 뒤 

포스터를 역순으로 보면서 이미 본 포스터는 업데이트 시켜주고 내가 보이는지 여부는 이미 업데이트 된 포스터들이 나를 완전히 가리는지 확인하면 된다.

이는 세그먼트 트리를 이용하여 업데이트 된 구간의 합을 찍어냄으로 판별 가능 하다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, seg[80040], lazy[80040], res;
pair<int, int> qry[10010];
vector<int> v;
int getx(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
void u_lazy(int node, int x, int y) {
    if (!lazy[node])
        return;
    seg[node] = (y - x + 1);
    if (x != y) {
        lazy[node * 2] = 1;
        lazy[node * 2 + 1] = 1;
    }
    lazy[node] = 0;
}
int update(int lo, int hi, int node, int x, int y) {
    u_lazy(node, x, y);
    if (y < lo || hi < x)return seg[node];
    if (lo <= x&&y <= hi) {
        lazy[node] = 1;
        u_lazy(node, x, y);
        return seg[node];
    }
    int mid = (x + y) >> 1;
    return seg[node] = update(lo, hi, node * 2, x, mid) + update(lo, hi, node * 2 + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    u_lazy(node, x, y);
    if (y < lo || hi < x)return 0;
    if (lo <= x&&y <= hi)return seg[node];
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * 2 + 1, mid + 1, y);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &qry[i].first, &qry[i].second);
        v.push_back(qry[i].first);
        v.push_back(qry[i].second);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = n - 1; i >= 0; i--) {
        int l = getx(qry[i].first);
        int r = getx(qry[i].second);
        int getsum = query(l, r, 1, 1, 2 * n);
        if (getsum != r - l + 1)res++;
        update(l, r, 1, 1, 2 * n);
    }
    printf("%d\n", res);
    return 0;
}