BOJ 28326 : 고기 파티

알고리즘

coor_comp, segtree

시간복잡도

$O((M+N)logN)$

풀이

우선 주어진 모든 좌표(고기의 시작/끝 좌표, 꼬치의 좌표)를 기준으로
좌표 압축을 진행한다. 가능한 값은 최대 $2(N+M)$ 개이다.

 

이제 각 쿼리별로 진행해보자. 한 꼬치에 꽂힐 수 있는 고기의 종류를
모두 알아내면 쉽게 정답을 구할 수 있다.
우선 고기를 시작 좌표 기준 오름차순으로 정렬한다. 이 경우
각 꼬치에 대해 1번 고기부터 특정 고기까지만 꽂힐 후보가 됨이 보장된다.

 

이제 고기 후보들 중 실제로 꼬치에 꽂히는 고기를 찾아보자.
{끝 좌표의 최댓값, 해당 고기}에 대한 segtree를 만들면,
위에서의 고기 후보 구간 내 끝 좌표가 가장 큰 고기를 알 수 있게 된다.
끝 좌표가 가장 큰 고기도 꼬치에 꽂히지 못할 때까지,
해당 고기 번호를 저장하고 segtree에서 빼내기를 반복하면 된다.
총 고기 수는 $N$개로 제한되어 있기에 시간복잡도는 $O(NlogN)$이다.

 

실제 출력하는 답은 두 꼬치에 모두 꽂히는 고기의 개수이기에,
1번째 꼬치에 꽂히는 고기를 저장한 후
해당 고기들을 다시 segtree에 넣어줘야 한다.
2번째 꼬치에 대해서도 똑같이 진행하고, 겹치는 고기만 출력 후
두 꼬치 중 하나라도 꽂힌 모든 고기를 segtree에서 빼주면 된다.

코드

#include <bits/stdc++.h>
using namespace std;

int N, Q, out[250005];
struct z
{
    int s, e, t;
}; z a[250005];
pair<int, int> ques[250005], tree[1000005];
vector<int> cp, assort, done;

bool comp(const z &l, const z &r)
{
    return l.s < r.s;
}

void make_tree(int now, int s, int e)
{
    if (s > e) return;
    if (s == e) {tree[now] = {a[s].e, s}; return;}
    int mid = s+e >> 1;
    make_tree(now*2, s, mid); make_tree(now*2+1, mid+1, e);
    tree[now] = tree[now*2 + (tree[now*2].first < tree[now*2+1].first)];
}

pair<int, int> Max(int now, int s, int e, int f, int r)
{
    if (s > e || r < s || e < f) return {-1, 0};
    if (f <= s && e <= r) return tree[now];
    int mid = s+e>>1;
    pair<int, int> ll = Max(now*2, s, mid, f, r), rr = Max(now*2+1, mid+1, e, f, r);
    return ll.first > rr.first ? ll : rr;
}

void update(int now, int s, int e, int p, int type)
{
    if (s > e || p < s || e < p) return;
    if (s == e) {tree[now] = {type ? a[s].e : -1, type ? s : 0};
    return;}
    int mid = s+e >> 1;
    update(now*2, s, mid, p, type);
    update(now*2+1, mid+1, e, p, type);
    tree[now]=tree[now*2+(tree[now*2].first< tree[now*2+1].first)];
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>N>>Q;
    for (int i = 1; i <= N; i++) {
        cin>>a[i].s>>a[i].e>>a[i].t; a[i].e--;
        cp.push_back(a[i].s); cp.push_back(a[i].e);
    }
    for (int i = 1; i <= Q; i++) {
        cin>>ques[i].first>>ques[i].second;
        cp.push_back(ques[i].first); cp.push_back(ques[i].second);
    }
    sort(cp.begin(), cp.end());
    cp.erase(unique(cp.begin(), cp.end()), cp.end());
    for (int i = 1; i <= N; i++) {
        a[i].s
        = lower_bound(cp.begin(), cp.end(), a[i].s)-cp.begin()+1;
        assort.push_back(a[i].s);
        a[i].e
        = lower_bound(cp.begin(), cp.end(), a[i].e)-cp.begin()+1;
    }
    for (int i = 1; i <= Q; i++) {
        ques[i].first = lower_bound(cp.begin(), cp.end(),
        ques[i].first)-cp.begin()+1;
        ques[i].second = lower_bound(cp.begin(), cp.end(),
        ques[i].second)-cp.begin()+1;
    }
    assort.push_back(-1);
    sort(assort.begin(), assort.end());
    sort(a+1, a+N+1, comp);
    make_tree(1, 1, N);
    for (int i = 1; i <= Q; i++) {
        done.clear();
        long long ans = 0; int p = upper_bound(assort.begin(),
        assort.end(), ques[i].first)-assort.begin()-1;
        while (1)
        {
            pair<int, int> M = Max(1, 1, N, 1, p);
            if (M.first < ques[i].first) break;
            out[M.second] = i;
            done.push_back(M.second);
            update(1, 1, N, M.second, 0);
        }
        for (int j = done.size()-1; j >= 0; j--)
            update(1, 1, N, done[j], 1);
        p = upper_bound(assort.begin(), assort.end(),
        ques[i].second)-assort.begin()-1;
        while (1)
        {
            pair<int, int> M = Max(1, 1, N, 1, p);
            if (M.first < ques[i].second) break;
            if (out[M.second] == i) ans += a[M.second].t;
            update(1, 1, N, M.second, 0);
        }
        for (int j = done.size()-1; j >= 0; j--)
            update(1, 1, N, done[j], 0);
        cout<<ans<<"\n";
    }
    return 0;
}