백준 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$_$p..
백준 30515 - 방형구 탐색 (Hard) (C++)
문제 문제 링크 BOJ 30515 - 방형구 탐색 (Hard) 문제 요약 $1*N$ 크기의 격자에서, 각 칸에 피어있는 꽃의 종류 $A_1, A_2, ... , A_N$가 주어진다. 아래 두 쿼리를 수행하는 프로그램을 작성하자. $1$ $l$ $r$ $k$ : $[l, r]$에서 꽃의 종류가 $k$인 꽃의 개수를 출력한다. $2$ $l$ $r$ : $[l, r]$에 속한 모든 꽃들을 제거한다. 제한 TL : $1.5$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 200,000$ $1 ≤ A_i$$, k ≤ 10^9$ $1$번 쿼리는 하나 이상 주어진다. 알고리즘 분류 자료 구조 (data_structures) 트리를 사용한 집합과 맵 (tree_set) 풀이 $EASY$버전을 나이브하게 짜고..