백준 20933 - 마스크펑크 2077 (C++)

문제

• 문제 링크

  
   BOJ 20933 - 마스크펑크 2077 
  

• 문제 요약

$N$개의 마을 각각에 대해, 마스크 생산 비용과 인접 마을 간 이동 시간이 주어진다.
아래 두 쿼리를 수행하는 프로그램을 작성하자.



$UPDATE$ $x$ $k$ : $x$번째 집과 $x+1$번째 집 사이의 이동 시간을 $k$분으로 갱신한다. $(1 ≤ x ≤ N-1$, $1 ≤ k ≤ 10^4)$

$CALL$ $x$ $k$ : $x$번째 집이 $k$분 이내에 얻을 수 있는 가장 싼 마스크의 가격을 출력한다. $(1 ≤ x ≤ N$, $1 ≤ k ≤ 10^6)$

• 제한

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




$2 ≤ N ≤ 10^5$

$1 ≤ Q ≤ 5*10^4$

알고리즘 분류

• 자료 구조 (data_structures)
• 세그먼트 트리 (segtree)
• 이분 탐색 (binary_search)

풀이

임의의 구간 $[l, r]$에서 $min(c_l, c_{l+1}, ... , c_r)$과 $\sum_{i=l}^{r-1}{t_i}$의 값을 빠르게 구할 수 있어야 한다.
또, $t_i$에 대해 점단위 업데이트도 처리할 수 있어야 한다.

이를 위해 각각의 상태를 관리할 두 개의 세그먼트 트리를 두자.

---

$CALL$ $x$ $k$ 에서, 왼 쪽으로 갈 수 있는 가장 먼 지점과 오른 쪽으로 갈 수 있는 가장 먼 지점을 찾자.
가능한 한 최소의 $c$를 찾는 데에 표본의 수는 최대한 많아야 좋으니 말이다.

이는 이분 탐색을 이용하면 쉽게 찾아줄 수 있다.

찾아진 구간 $[l, r]$에 대해, $c_i$를 관리하는 세그먼트 트리로 최솟값을 찾으면 되겠다.

적당한 $[l, r]$을 찾는데에 $O(log^2N)$, $[c_l, c_r]$에서 최솟값을 찾는데에 $O(logN)$으로 문제를 총 $O(Qlog^2N)$에 풀 수 있다.

구현해야 할 코드가 적은 편은 아니니 실수하지 않도록 유의하자.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int n, seg[200005], mseg[200005];
void init()
{
    for (int i(n - 1); i; i--)
    {
        mseg[i] = min(mseg[i << 1], mseg[i << 1 | 1]);
        seg[i] = seg[i << 1] + seg[i << 1 | 1];
    }
}
void update(int idx, int val)
{
    seg[idx + n] = val;
    for (idx += n; idx > 1; idx >>= 1)
        seg[idx >> 1] = seg[idx] + seg[idx ^ 1];
}
int squery(int l, int r, int res = 0)
{
    for (l += n, r += n; l < r; l >>= 1, r >>= 1)
    {
        if (l & 1) res += seg[l++];
        if (r & 1) res += seg[--r];
    }
    return res;
}
int mquery(int l, int r, int res = 1e9)
{
    for (l += n, r += n; l < r; l >>= 1, r >>= 1)
    {
        if (l & 1) res = min(res, mseg[l++]);
        if (r & 1) res = min(res, mseg[--r]);
    }
    return res;
}
int getLidx(int x, int k)
{
    int l(1), r(x), res(x + 1);
    while (l <= r)
    {
        int m(l + r >> 1);
        if (squery(m, x + 1) <= k) r = (res = m) - 1;
        else l = m + 1;
    }
    return res;
}
int getRidx(int x, int k)
{
    int l(x), r(n - 1), res(x - 1);
    while (l <= r)
    {
        int m(l + r >> 1);
        if (squery(x, m + 1) <= k) l = (res = m) + 1;
        else r = m - 1;
    }
    return res;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i{}; i < n; cin >> mseg[i++ + n]);
    for (int i(1); i < n; cin >> seg[i++ + n]);
    init();
 
    int q; cin >> q;
    while (q--)
    {
        string op; cin >> op;
        int x, k; cin >> x >> k;
        if (op == "UPDATE") update(x, k);
        else
        {
            int lidx(getLidx(x - 1, k));
            int ridx(getRidx(x, k));
            cout << mquery(lidx - 1, ridx + 1) << '\n';
        }
    }
}

comment

끝