[BOJ 15506 // C++] 정원사

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

 

이번에 볼 문제는 백준 15506번 문제인 정원사이다.
문제는 아래 링크를 확인하자.

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

15506번: 정원사

매일 높이가 일정하게 자라므로, 식물의 높이를 "0일째의 높이 기준"으로 관리하면 편하게 문제를 해결할 수 있게 된다.

 

range sum query와 range max query를 다룰 수 있는 세그먼트트리를 구현하여 문제를 해결하자.

 

이 문제에서는 같은 노드에 식물이 여러 개 자랄 수 있고 이들을 모두 관리해줄 필요가 있는데, 이는 세그먼트트리의 각 리프노드를 우선순위 큐를 이용해 구현할 수 있다.

 

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

#define INF 1000000000000000000LL
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

int N, Q; ll K;
priority_queue<ll> pq[100001];
pair<ll, ll> seg[262145]; // {구간 식물수, 최대높이}

void init(int L, int R, int sI) {
	seg[sI] = make_pair(0, -INF);
	if (L < R) init(L, (L + R) / 2, sI * 2), init((L + R) / 2 + 1, R, sI * 2 + 1);
}

pair<ll, ll> upd(int L, int R, int qI, ll qV, int sI) {
	if (qI < L || R < qI) return seg[sI];
	if (L == R) {
		pq[L].push(qV);
		return seg[sI] = make_pair(pq[L].size() - 1, pq[L].top());
	}
	auto p1 = upd(L, (L + R) / 2, qI, qV, sI * 2), p2 = upd((L + R) / 2 + 1, R, qI, qV, sI * 2 + 1);
	return seg[sI] = make_pair(p1.first + p2.first, max(p1.second, p2.second));
}

pair<ll, ll> rmvqry(int L, int R, int qL, int qR, ll qV, int sI) { // 최댓값, 인덱스
	if (R < qL || qR < L) return seg[sI];
	if (qL <= L && R <= qR) {
		if (seg[sI].second <= qV) return seg[sI];
		if (L == R) {
			while (pq[L].top() > qV) pq[L].pop();
			return seg[sI] = make_pair(pq[L].size() - 1, pq[L].top());;
		}
		else {
			auto p1 = rmvqry(L, (L + R) / 2, qL, qR, qV, sI * 2), p2 = rmvqry((L + R) / 2 + 1, R, qL, qR, qV, sI * 2 + 1);
			return seg[sI] = make_pair(p1.first + p2.first, max(p1.second, p2.second));
		}
	}
	auto p1 = rmvqry(L, (L + R) / 2, qL, qR, qV, sI * 2), p2 = rmvqry((L + R) / 2 + 1, R, qL, qR, qV, sI * 2 + 1);
	return seg[sI] = make_pair(p1.first + p2.first, max(p1.second, p2.second));
}

ll rangesum(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI].first;
	return rangesum(L, (L + R) / 2, qL, qR, sI * 2) + rangesum((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> Q >> K;
	for (int i = 1; i <= N; i++) pq[i].push(-INF);

	while (Q--) {
		int q; cin >> q;
		if (q == 1) {
			ll t, h; int x; cin >> t >> x >> h;
			h -= t * K;
			upd(1, N, x, h, 1);
		}
		else if (q == 2) {
			ll t, h; int l, r; cin >> t >> l >> r >> h;
			h -= t * K;
			rmvqry(1, N, l, r, h, 1);
		}
		else {
			ll t; int l, r; cin >> t >> l >> r;
			cout << rangesum(1, N, l, r, 1) << '\n';
		}
	}
}