백준 30512 - 조용히 완전히 영원히 (C++)

문제

• 문제 링크

  
   BOJ 30512 - 조용히 완전히 영원히 
  

• 문제 요약

길이 $N$의 수열 $A_1, A_2, ... , A_N$이 주어진다.
아래 쿼리가 $Q$개 주어질 때, $Q$개의 쿼리를 순서대로 처리한 후의 수열과 각 쿼리마다 잊힌 원소의 개수를 구해보자.



$L$ $R$ $x$ : 모든 $L ≤ i ≤ R$에 대해 $A_i = min(A_i, x)$를 적용한다.

• 제한

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




$1 ≤ N, Q ≤ 100,000$

$0 ≤ A_i, x ≤ 1,000,000$

알고리즘 분류

• 자료 구조 (data_structures)
• 세그먼트 트리 (segtree)
• 느리게 갱신되는 세그먼트 트리 (lazy_propagation)

풀이

구간 업데이트답게 무지성 $lazy$_$propagation$을 구현하자.

구체적으로 각 노드에서 { 현재 값, 마지막으로 영향을 받은 쿼리의 번호 } 를 관리하면 된다.

$Q$번의 업데이트 이후, $propagation$ 연산을 적절히 수행하면 최종 수열의 모습과 $D_1, D_2, ... D_Q$를 구할 수 있다.

각 $D_i$를 구할 땐 최종 수열을 정렬한 뒤 세주는 것이 편하다.


이외에 정말 다양한 풀이들이 존재해 보인다.

$lazy$를 안쓰는 풀이도, 쿼리를 정렬해 $segtree$ 자체를 안쓰는 풀이도 있는 듯 하다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
struct { int val = 1e9, idx = 1e9; } lz[1 << 18];
vector <int> D, seg(1 << 18, 1e9);
 
void prop(int n, int s, int e)
{
    auto& [val, idx](lz[n]);
    if (idx == 1e9) return;
    if (seg[n] > val)
    {
        if (s == e) D[s] = idx;
        seg[n] = val;
    }
    if (s ^ e)
    {
        if (lz[n << 1].val > val) lz[n << 1] = { val, idx };
        if (lz[n << 1 | 1].val > val) lz[n << 1 | 1] = { val, idx };
    }
    idx = 1e9;
}
int update(int n, int s, int e, int l, int r, int val, int idx)
{
    prop(n, s, e);
    if (s > r || e < l) return seg[n];
    if (s >= l && e <= r)
    {
        lz[n] = { val, idx };
        prop(n, s, e);
        return seg[n];
    }
    int m(s + e >> 1);
    return seg[n] = min(update(n << 1, s, m, l, r, val, idx), update(n << 1 | 1, m + 1, e, l, r, val, idx));
}
int query(int n, int s, int e, int i)
{
    prop(n, s, e);
    if (s > i || e < i) return 1e9;
    if (s == e) return seg[n];
    int m(s + e >> 1);
    return min(query(n << 1, s, m, i), query(n << 1 | 1, m + 1, e, i));
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
 
    D.resize(n + 1);
    for (int i(1); i <= n; i++)
    {
        int val; cin >> val;
        update(1, 1, n, i, i, val, 0);
    }
 
    int q; cin >> q;
    for (int i(1); i <= q; i++)
    {
        int l, r, val; cin >> l >> r >> val;
        update(1, 1, n, l, r, val, i);
    }
 
    for (int i(1); i <= n; i++)
        cout << query(1, 1, n, i) << ' ';
    cout << '\n';
 
    sort(D.begin(), D.end());
    for (int cnt{}, i(1), j(1); i <= q; i++)
    {
        while (j <= n && D[j] <= i) cnt++, j++;
        cout << cnt << ' ';
    }
}

comment

끝