[G3] 백준 2370번 시장 선거 포스터 C++ 정렬, 이분 탐색, 느리게 갱신되는 세그먼트 트리, 값/좌표 압축, set

리뷰

 

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

골드 3문제가 맞나 싶다. multiset으로 풀이하려 했으나 실패하고, 값/좌표 압축과 구간 업데이트 세그트리로 풀이했다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 포스터의 개수를 저장할 변수
• cs : 포스터의 시작과 끝 좌표를 저장할 벡터
• xs : 등장한 좌표를 저장할 벡터
• tree : 세그먼트 트리 정보를 저장할 배열
• lazy : 업데이트 정보를 저장할 배열
• ans : 최종 포스터 인덱스를 저장할 집합

 

함수

1. propagte

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 v) {
	if (R < s || e < L) return;
	if (L <= s && e <= R) {
		lazy[node] = v;
		propagate(node, s, e);
		return;
	}
	propagate(node, s, e);
	int mid = (s + e) / 2;
	update(node * 2, s, mid, L, R, v);
	update(node * 2 + 1, mid + 1, e, L, R, v);
	tree[node] = tree[node * 2] == tree[node * 2 + 1] ? tree[node * 2] : 0;
}

 

구간 업데이트 정보를 lazy배열에 전달하고, 자식 노드의 값이 같다면 상위 노드도 업데이트 해주기 위한 함수

 

3. query

void query(int node, int s, int e, int L, int R) {
	propagate(node, s, e);
	if (tree[node]) ans.insert(tree[node]);
	if (s == e) return;
	else {
		int mid = (s + e) / 2;
		query(node * 2, s, mid, L, R);
		query(node * 2 + 1, mid + 1, e, L, R);
	}
}

 

최종 포스터 정보를 저장하기 위한 함수

 

 

문제풀이

n값을 입력 받고, n개의 포스터 정보를 입력 받아 cs, xs벡터를 초기화한다.

 

 

트러블 슈팅

없음

 

 

참고 사항

1. (1 ≤ l < r ≤ 100,000,000)이므로 값/좌표 압축을 사용하지 않고는 배열 인덱스로 구현이 불가능하다.
2. 구간 업데이트 처리가 필요하여 느리게 갱신되는 세그먼트 트리를 사용했다.
3. 1-based-indexing을 사용하기 위해 xs에 임의의 값 0을 추가해두었다.
4. 값/좌표 압축을 했기에 존재하지 않는 인덱스는 없겠지만 혹시 몰라 ans에 0이 있을 경우 제거해주었다.
5. 값/좌표 압축 후 인덱스의 최대값은 N*2이다. 따라서 세그먼트 트리 범위를 n이 아닌 xs의 크기로 지정해야한다.

 

정답 코드

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

const int N = 2e4 + 1;
int n;
vector<pii> cs;
vector<int> xs;
int tree[N * 4];
int lazy[N * 4];
set<int> ans;

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 v) {
	if (R < s || e < L) return;
	if (L <= s && e <= R) {
		lazy[node] = v;
		propagate(node, s, e);
		return;
	}
	propagate(node, s, e);
	int mid = (s + e) / 2;
	update(node * 2, s, mid, L, R, v);
	update(node * 2 + 1, mid + 1, e, L, R, v);
	tree[node] = tree[node * 2] == tree[node * 2 + 1] ? tree[node * 2] : 0;
}

void query(int node, int s, int e, int L, int R) {
	propagate(node, s, e);
	if (tree[node]) ans.insert(tree[node]);
	if (s == e) return;
	else {
		int mid = (s + e) / 2;
		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 l, r; cin >> l >> r;
		cs.push_back({ l, r });
		xs.push_back(l);
		xs.push_back(r);
	}

	xs.push_back(0);
	sort(xs.begin(), xs.end());
	xs.erase(unique(xs.begin(), xs.end()), xs.end());

	int m = xs.size();
	for (int i = 1; i <= n; ++i) {
		pii c = cs[i - 1];
		int l = c.first, r = c.second;
		int li = lower_bound(xs.begin(), xs.end(), l) - xs.begin();
		int ri = lower_bound(xs.begin(), xs.end(), r) - xs.begin();
		update(1, 1, m, li, ri, i);
	}
	query(1, 1, m, 1, m);
	if (ans.count(0)) ans.erase(0);
	cout << ans.size();
}