[P3] 백준 18407번 가로 블록 쌓기 C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리, 값/좌표 압축

리뷰

 

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

간만에 풀어본 느갱세 문제, 여전히 재밌다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 블록의 개수를 저장할 변수
• xs : 값/좌표 매핑을 하기 위한 map
• qs : 쿼리 정보를 저장할 배열
• tree : 세그먼트 트리 정보를 저장할 벡터
• lazy : 트리 갱신 정보를 저장할 벡터

 

함수

1. propagate

void propagate(int node, int s, int e) {
	if (lazy[node]) {
		tree[node] = lazy[node];

		if (s != e) {
			lazy[node * 2] = lazy[node];
			lazy[node * 2 + 1] = lazy[node];
		}

		lazy[node] = 0;
	}
}

 

현재 노드에 lazy값이 있다면 세그트리에 적용하고, 리프노드가 아닐 경우 하위 노드에 전파하기 위한 함수

 

2. update

void update(int node, int s, int e, int L, int R, int x) {
	if (R < s || e < L) return;
	propagate(node, s, e);
	if (L <= s && e <= R) {
		lazy[node] = x;
		propagate(node, s, e);
		return;
	}
	int mid = (s + e) / 2;
	update(node * 2, s, mid, L, R, x);
	update(node * 2 + 1, mid + 1, e, L, R, x);
	tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}

 

세그트리 구간 업데이트를 수행하기 위한 함수

 

3. query

int query(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return 0;
	propagate(node, s, e);
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	return max(query(node * 2, s, mid, L, R), query(node * 2 + 1, mid + 1, e, L, R));
}

 

세그트리의 구간 최대값을 구하기 위한 함수

 

 

문제풀이

1. n값을 입력 받고, n개의 가로 블록 정보를 입력 받아 xs, qs를 초기화한다.
2. 변수 idx를 0으로 초기화 하고, xs를 순회하며 각 key의 value값을 idx를 전위증가한 값으로 교체한다.
3. 변수 len에 xs의 size()를 저장하고, tree, lazy를 각각 (len+1)*4크기로, 값은 0으로 초기화한다.
4. n개의 가로 블록 정보를 순회하며 변수 L, R에 압축된 인덱스를 저장한다.
5. 변수 mx에 query함수를 통해 L~R범위의 최대값을 구해 저장한다.
6. update함수를 통해 L~R범위의 값을 mx+1로 업데이트 처리한다.
7. 모든 블록을 순차적으로 쌓은 후에 query함수를 통해 세그먼트 트리의 전 구간에서의 최대값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. tree, lazy의 경우 n으로 최대 구간을 지정하는게 아닌 xs의 크기를 기반으로 최대 구간을 지정해 주어야 한다.
2. xs의 idx가 1부터 시작하므로 tree, lazy도 1-based-indexing으로 초기화 및 구간 질의 처리를 해주었다.
3. 종료 좌표는 -1처리를 해주어 블록의 시작 좌표와 종료 좌표가 겹치지 않도록 해주었다.

 

정답 코드

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
using pii = pair<int, int>;

const int N = 1e5;
int n;
map<int, int> xs;
pii qs[N];
vector<int> tree;
vector<int> lazy;

void propagate(int node, int s, int e) {
	if (lazy[node]) {
		tree[node] = lazy[node];

		if (s != e) {
			lazy[node * 2] = lazy[node];
			lazy[node * 2 + 1] = lazy[node];
		}

		lazy[node] = 0;
	}
}

void update(int node, int s, int e, int L, int R, int x) {
	if (R < s || e < L) return;
	propagate(node, s, e);
	if (L <= s && e <= R) {
		lazy[node] = x;
		propagate(node, s, e);
		return;
	}
	int mid = (s + e) / 2;
	update(node * 2, s, mid, L, R, x);
	update(node * 2 + 1, mid + 1, e, L, R, x);
	tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}

int query(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return 0;
	propagate(node, s, e);
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	return max(query(node * 2, s, mid, L, R), query(node * 2 + 1, mid + 1, e, L, R));
}

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

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int w, d; cin >> w >> d;
		int s = d, e = d + w - 1;
		xs[s];
		xs[e];
		qs[i] = { s, e };
	}

	int idx = 0;
	for (auto& x : xs) x.second = ++idx;
	int len = xs.size();
	tree.resize((len + 1) * 4, 0);
	lazy.resize((len + 1) * 4, 0);

	for (int i = 0; i < n; ++i) {
		int L = xs[qs[i].first], R = xs[qs[i].second];
		//cout << L << " " << R << "\n";
		int mx = query(1, 1, len, L, R);
		update(1, 1, len, L, R, mx + 1);
	}
	cout << query(1, 1, len, 1, len);
}