취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 30512번 문제인 조용히 완전히 영원히이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/30512

글쓴이는 이 문제를 쿼리를 $L$ 기준으로 정렬 후 sweeping하는 방향으로 접근하였다.

$A_1$부터 $A_N$까지 수열을 구성하는 수를 하나씩 차례대로 보면서 문제를 해결해보자.

이 과정에서 각 $i$번째 수를 포함하는 쿼리는 $i-1$번째 수를 포함하는 구간쿼리에서 $i-1$번째 수까지만 포함하는 쿼리를 제외 및 $i$번째 수부터 포함하는 쿼리를 추가한 쿼리들로 구성되어 있음을 관찰하자. 또한 이러한 쿼리의 추가 및 제외는 총 $2N$번 이하로 나타남을 관찰하자.

한편, 이와 같은 쿼리 중 해당 수에 마지막으로 유의미하게 적용되었을 수 있는 쿼리는 (1) 적용하고자 하는 $x$값이 가장 작은 쿼리, 그러한 쿼리가 여러 개면 (2) 가장 먼저 적용된 쿼리 하나만 확인해도 충분함을 관찰하자. 그 이전에 적용한 쿼리는 해당 쿼리로 무조건 그 덮어씌워질 것이고, 그 이후의 쿼리는 해당 쿼리의 결과를 바꾸지 못할 것이기 때문이다. 물론, 해당 쿼리도 값을 바꾸지 못하는 경우도 존재하는데(원래 값이 매우 작았던 경우가 이에 해당한다.), 이 경우에는 어떤 쿼리도 값을 바꾸지 않는다는 것을 알 수 있다.

위와 같은 쿼리의 추가, 제거 및 탐색은 우선순위 큐(Priority Queue)를 이용해 어렵지 않게 구현할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
using namespace std;

int N, Q;
int A[100001];
priority_queue<pair<pair<int, int>, pair<int, int>>> pq;
priority_queue<pair<pair<int, int>, int>> pq2;
int ans[100001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];
	cin >> Q;
	for (int q = 1; q <= Q; q++) {
		int L, R, V; cin >> L >> R >> V;
		pq.push(make_pair(make_pair(-L, R), make_pair(V, q)));
	}
	for (int i = 1; i <= N; i++) {
		while (!pq.empty() && pq.top().first.first == -i) {
			pq2.push(make_pair(make_pair(-pq.top().second.first, -pq.top().second.second), pq.top().first.second));
			pq.pop();
		}
		while (!pq2.empty() && pq2.top().second < i) pq2.pop();
		if (!pq2.empty()) {
			if (-pq2.top().first.first < A[i]) ans[-pq2.top().first.second]++, A[i] = -pq2.top().first.first;
			else ans[0]++;
		}
		else ans[0]++;
	}
	for (int i = 1; i <= N; i++) cout << A[i] << ' ';
	cout << '\n';
	for (int i = 1; i <= Q; i++) {
		ans[i] += ans[i - 1];
		cout << ans[i] << ' ';
	}
}