[BOJ 20212] 나무는 쿼리를 싫어해~(c++)

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

---

문제 개요

길이가 N인 수열이 주어질 때, 다음 두 종류의 쿼리를 처리하는 문제입니다.

• 1번 쿼리: Ai, Ai+1, ..., Aj에 k를 더한다.
• 2번 쿼리: k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ..., Aj의 합을 출력한다.

특이점은 수열의 범위가 1부터 10억까지로 매우 크다는 점입니다. 수열의 모든 항들의 초기값은 0입니다.

• (2 ≤ N ≤ 50,000)
• (1 ≤ i ≤ j ≤ 1,000,000,000)
• (-100,000 ≤ k ≤ 100,000 for 1번 쿼리)

---

문제 풀이

이 문제는 좌표 압축과 Lazy Propagation을 활용한 세그먼트 트리로 해결하였습니다.

핵심 아이디어는 다음과 같습니다.

1. 좌표 압축: 수열의 범위가 10억으로 매우 크지만, 실제로 쿼리에서 사용되는 구간은 최대 50,000개입니다. 따라서 쿼리에서 사용되는 모든 좌표(시작점과 끝점+1)를 수집하여 압축합니다.

1. 2번 쿼리 정렬: 2번 쿼리를 k값 기준으로 정렬합니다. 이렇게 하면 k번째까지의 1번 쿼리를 순차적으로 적용하면서 모든 2번 쿼리를 효율적으로 처리할 수 있습니다.

1. Lazy Propagation: 구간 업데이트를 효율적으로 처리하기 위해 Lazy Propagation 기법을 사용합니다. 세그먼트 트리의 각 노드는 해당 구간의 합을 저장하고, lazy 배열은 아직 전파되지 않은 업데이트 값을 저장합니다.

1. 구간 합 계산: 좌표 압축된 인덱스를 사용하여 세그먼트 트리에서 구간 [x, y]의 합을 계산합니다. 세그먼트 트리의 각 노드는 해당 구간의 실제 길이(v[e+1] - v[s])를 고려하여 합을 계산합니다.

좌표 압축 시 y+1을 함께 저장하는 이유는 구간 [x, y]를 반열린구간 [x, y+1)로 처리하여 구간 경계를 명확히 하기 위함입니다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class s_node {
public:
	int x, y, k;
};

class q_node {
public:
	int x, y, k, idx;
};

vector<s_node> sq;
vector<q_node> qq;
vector<int> v;

vector<long long> seg;
vector<long long> lazy;

int n, m;

bool cmp(q_node a, q_node b) {
	return a.k < b.k;
}

void lazy_propagation(int x, int s, int e) {
	if (lazy[x]) {
		seg[x] += lazy[x] * (v[e + 1] - v[s]);
		if (s != e) {
			for (int i = x * 2; i <= x * 2 + 1; i++) {
				lazy[i] += lazy[x];
			}
		}
		lazy[x] = 0;
	}
}

long long update(int x, int s, int e, int l, int r, long long v) {
	lazy_propagation(x, s, e);
	if (r < s || e < l) return seg[x];
	if (l <= s && e <= r) {
		lazy[x] += v;
		lazy_propagation(x, s, e);
		return seg[x];
	}
	int mid = s + (e - s) / 2;
	return seg[x] = update(x * 2, s, mid, l, r, v) + update(x * 2 + 1, mid + 1, e, l, r, v);
}

int get_coord(int x) {
	x = lower_bound(v.begin(), v.end(), x) - v.begin();
	return x;
}

long long query(int x, int s, int e, int l, int r) {
	lazy_propagation(x, s, e);
	if (r < s || e < l) return 0;
	if (l <= s && e <= r) return seg[x];
	int mid = s + (e - s) / 2;
	return query(x * 2, s, mid, l, r) + query(x * 2 + 1, mid + 1, e, l, r);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int r_idx = 0;
	int cmd, x, y, k;
	sq.reserve(n);
	qq.reserve(n);
	v.reserve(n * 2);
	for (int i = 0; i < n; i++) {
		cin >> cmd >> x >> y >> k;
		v.push_back(x);
		v.push_back(y + 1);
		if (cmd == 1) {
			sq.push_back({ x, y, k });
		}
		else {
			qq.push_back({ x, y, k, r_idx++ });
		}
	}
	vector<long long> res(r_idx);
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	sort(qq.begin(), qq.end(), cmp);
	int idx = 0;
	int m = v.size();
	seg.resize(m * 4, 0);
	lazy.resize(m * 4, 0);
	for(int i = 0; i < qq.size(); i++){
		while (idx < sq.size() && idx < qq[i].k) {
			int x = get_coord(sq[idx].x);
			int y = get_coord(sq[idx].y + 1) - 1;
			long long v = sq[idx].k;
			idx++;
			update(1, 0, m - 1, x, y, v);
		}
		int x = get_coord(qq[i].x);
		int y = get_coord(qq[i].y + 1) - 1;
		long long ret = query(1, 0, m - 1, x, y);
		res[qq[i].idx] = ret;
	}
	for (auto x : res) {
		cout << x << '\n';
	}
	return 0;
}