[P2] 백준 20212번 나무는 쿼리를 싫어해~ C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리, 오프라인 쿼리, 정렬, 값/좌표 압축, 우선순위 큐

리뷰

 

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

값/좌표 압축에 애좀 먹은 문제, 닫힌 구간과 열린 구간에 대한 개념을 새로 익힌 문제였다.

 

 

전역 변수

• n : 쿼리의 개수를 저장할 변수
• Q1 : 1번 쿼리를 정의할 구조체
• Q2 : 2번 쿼리를 정의할 구조체, k를 기준으로 오름차순 정렬한다.
• tree : 세그먼트 트리 정보를 저장할 벡터
• lazy : 세그먼트 트리 갱신 정보를 저장할 벡터
• cs : 압축된 값을 저장할 벡터

 

함수

1. propagate

void propagate(int node, int s, int e) {
	if (lazy[node]) {
		tree[node] += lazy[node] * (cs[e + 1] - cs[s]);
		
		if (s != e) {
			lazy[node * 2] += lazy[node];
			lazy[node * 2 + 1] += lazy[node];
		}

		lazy[node] = 0;
	}
}

 

트리 갱신 정보가 존재할 경우 현재 노드에 업데이트를 처리하고, 자식 노드에 전파하기 위한 함수

 

2. update

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

 

세그먼트 트리 업데이트를 위한 함수

 

3. query

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

 

세그먼트 트리 구간 합을 구하기 위한 함수

 

4. get_range

pair<int, int> get_range(int i, int j) {
	int L = lower_bound(cs.begin(), cs.end(), i) - cs.begin();
	int R = lower_bound(cs.begin(), cs.end(), j + 1) - cs.begin();
	return { L, R - 1 };
}

 

값을 기반으로 세그먼트 트리 열린 구간을 구하기 위한 함수

 

 

문제풀이

1. n값을 입력 받고, Q1타입의 큐 q1와 Q2타입의 큐 q2를 초기화한다.
2. 변수 q2_cnt를 0으로 초기화하고, long long타입 벡터 ans를 초기화한다.
3. n개의 쿼리 정보를 입력 받아 각 좌표 값을 cs에 push한다. 이때 j의 경우 +1처리하여 열린 구간으로 처리한다.
4. 1번 쿼리일 경우 q1에 push하고, 2번 쿼리일 경우 q2에 push하되 q2_cnt를 통해 출현 인덱스도 같이 저장한다.
5. sort함수를 통해 cs벡터를 오름차순으로 정렬하고, erase와 unique를 통해 중복값을 제거한다.
6. 변수 m에 cs의 크기를 저장하고, tree, lazy를 m*4크기로 초기화한다.
7. ans의 크기는 q2_cnt로 초기화 하고, 변수 q1_cnt를 0으로 초기화한다.
8. q1, q2가 모두 빌때까지를 조건으로 하는 while루프를 수행한다.
9. 먼저 q2가 비지 않았고, q2의 top()요소의 k값이 q1_cnt와 동일하다면 쿼리 2에 대한 처리를 수행한다.
10. 변수 L, R에 get_range함수에 현재 요소의 i, j를 전달하여 세그먼트 트리 구간을 파싱한다.
11. ans[q.idx]에 query함수를 통해 세그먼트 트리 L, R구간합을 저장하고, continue처리한다.
12. 위 조건에 해당하지 않고, q1이 빈 상태가 아니라면 쿼리 1에 대한 처리를 수행한다.
13. q1_cnt를 증가시키고, 변수 L, R에 get_range함수에 현재 요소의 i, j를 전달하여 세그먼트 트리 구간을 파싱한다.
14. update함수를 통해 L, R범위에 k*각 구간의 길이 만큼 더해준다.
15. 모든 탐색을 마친 후 ans에 저장된 값을 줄 바꿈을 기준으로 구분하여 출력한다.

 

트러블 슈팅

1. 세그먼트 트리의 리프 노드를 각 좌표의 점으로 생각하고 구현하였더니 계속 예제를 맞히지 못했다.
2. 리프 노드를 각 구간의 길이 합으로 생각하고 구현하였더니 AC를 받았다.

 

참고 사항

1. i~j을 입력 받았을때 j를 +1처리하여 끝 점으로 생각하고, 세그 트리의 리프노드는 구간의 합으로 생각한다.
2. 따라서 lower_bound로 구간 L, R을 구할 때 R은 -1처리를 해주어야 올바른 구간을 구할 수 있다.

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;

int n;
struct Q1 {
	int i, j, k;
};
struct Q2 {
	int i, j, k, idx;
	bool operator<(const Q2& other) const {
		return k > other.k;
	}
};
vector<ll> tree;
vector<ll> lazy;
vector<int> cs;

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

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

pair<int, int> get_range(int i, int j) {
	int L = lower_bound(cs.begin(), cs.end(), i) - cs.begin();
	int R = lower_bound(cs.begin(), cs.end(), j + 1) - cs.begin();
	return { L, R - 1 };
}

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

	cin >> n;
	queue<Q1> q1;
	priority_queue<Q2> q2;
	int q2_cnt = 0;
	vector<ll> ans;
	
	while (n--) {
		int o, i, j, k; cin >> o >> i >> j >> k;
		cs.push_back(i);
		cs.push_back(j + 1);
		if (o == 1) q1.push({ i, j, k });
		else q2.push({ i, j, k, q2_cnt++ });
	}

	sort(cs.begin(), cs.end());
	cs.erase(unique(cs.begin(), cs.end()), cs.end());
	int m = cs.size();

	tree.resize(m * 4, 0);
	lazy.resize(m * 4, 0);
	ans.resize(q2_cnt, 0);
	int q1_cnt = 0;
	while (!q1.empty() || !q2.empty()) {
		if (!q2.empty() && q2.top().k == q1_cnt) {
			Q2 q = q2.top(); q2.pop();
			int i = q.i, j = q.j, k = q.k;

			auto [L, R] = get_range(i, j);
			ans[q.idx] = query(1, 0, m - 2, L, R);
			continue;
		}

		if (!q1.empty()) {
			++q1_cnt;
			Q1 q = q1.front(); q1.pop();
			int i = q.i, j = q.j, k = q.k;

			auto [L, R] = get_range(i, j);
			update(1, 0, m - 2, L, R, k);
		}
	}
	for (ll i : ans) cout << i << "\n";
}