백준 30943 - Zatopljenje (C++)

문제

• 문제 링크

  
   BOJ 30943 - Zatopljenje 
  

• 문제 요약

$N$개의 지점에 대해 $h_1, h_2, ... , h_N$이 주어진다.
아래 쿼리를 수행하는 프로그램을 작성해보자.



$l$ $r$ $x$ : 해수면이 $x$까지 차올랐을 때, $[l, r]$에서 볼 수 있는 섬의 개수를 출력한다.


만약 인접한 섬이 모두 보인다면, 이는 하나로 쳐야 한다.


• 제한

TL : $2$ sec, ML : $1024$ MB




$1 ≤ N, Q ≤ 200,000$

$0 ≤ h_i, x ≤ 10^9$

알고리즘 분류

• 자료 구조(data_structures)
• 세그먼트 트리(segtree)
• 오프라인 쿼리(offline_queries)

풀이

온라인으로 풀기엔 좀 난감해 보인다. 쿼리를 순차적으로 처리할 때, $x$가 단조성을 가진다면 좀 편해지지 않을까?

나같은 경우 모든 쿼리를 $x$ 기준 내림차순 정렬하여 답을 계산하였다.

이러면 $Q_1$을 계산하는 시점에 섬으로 존재하던 지점들은 $Q_2, Q_3, ... , Q_q$에서도 섬으로 존재하게 된다.

이 상태 변화를 세그먼트 트리를 이용해 관리해주자.

---

한편, $[l, r]$에 존재하는 섬의 개수는 어떻게 구할 수 있을까?

위에서 정리한 흐름을 생각했을 때, 간단히 합 쿼리를 이용해 구할 수 있을 것 같다.

그럼 결국 우리가 풀어야할 최종 문제는 "인접한 섬을 어떻게 취합할 것인가?"가 된다.

적당한 고민 끝에, 세그먼트 트리의 각 노드에서 $3$개의 값 $l, r, cnt$을 관리하면 될 것 같다는 결론이 섰다.

$l$ : 현재 세그먼트 트리가 $[s, e]$를 관리할 때, $s$번 섬이 보이고 있는가?

$r$ : 현재 세그먼트 트리가 $[s, e]$를 관리할 때, $e$번 섬이 보이고 있는가?

$cnt$ : 현재 세그먼트 트리가 $[s, e]$를 관리할 때, 몇 개의 섬이 보이고 있는가?

이 경우 두 구간 $L$, $R$이 $merge$되어 $res$로 될 때의 변화는 아래와 같을 것이다.

$res.l$ : $L.l$

$res.r$ : $R.r$

$res.cnt$ : $L.cnt$ + $R.cnt$에서 $L.r$, $R.l$이 켜져 있다면 $-1$

최종적으로 $O((N+Q)logN + QlogQ)$의 복잡도로 문제를 해결할 수 있다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
struct S { bool l, r; int cnt; } seg[1 << 19];
S merge(const S& L, const S& R)
{
    S res{ L.l, R.r, L.cnt + R.cnt - (L.r && R.l) };
    return res;
}
S update(int n, int s, int e, int i)
{
    if (s > i || e < i) return seg[n];
    if (s == e) return seg[n] = { 1, 1, 1 };
    int m(s + e >> 1);
    return seg[n] = merge(update(n << 1, s, m, i), update(n << 1 | 1, m + 1, e, i));
}
S query(int n, int s, int e, int l, int r)
{
    if (s > r || e < l) return { 0, 0, 0 };
    if (s >= l && e <= r) return seg[n];
    int m(s + e >> 1);
    return merge(query(n << 1, s, m, l, r), query(n << 1 | 1, m + 1, e, l, r));
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
 
    vector <pair<int, int>> h;
    for (int i(1); i <= n; i++)
    {
        int x; cin >> x;
        h.emplace_back(x, i);
    }
    sort(h.begin(), h.end(), greater<>());
 
    vector <tuple <int, int, int, int>> Q(q);
    for (int i{}; auto& [x, l, r, idx] : Q)
    {
        cin >> l >> r >> x;
        idx = i++;
    }
    sort(Q.begin(), Q.end(), greater<>());
 
    vector <int> ans(q);
    for (int i{}, hi{}; i < q; i++)
    {
        auto& [x, l, r, idx](Q[i]);
        while (hi < n && h[hi].first > x)
            update(1, 1, n, h[hi++].second);
 
        ans[idx] = query(1, 1, n, l, r).cnt;
    }
 
    for (int i{}; i < q; cout << ans[i++] << '\n');
}

comment

끝