백준 16978번 수열과 쿼리 22 C++ 세그먼트 트리, 오프라인 쿼리

리뷰

쿼리와 업데이트를 모두 미리 받아준 다음 각 업데이트에 시점에 맞는 쿼리를 출력하는 문제

우선순위 큐를 썼다가, 다른 요소까지 정렬이 되는 이유로 인해 오답을 맞아 sort를 사용했다.

이후 int 범위를 넘어가는 케이스가 있어 long long 타입으로 변경하니 통과하였다.

 

문제 풀이

1. n값을 입력 받고 lst에 수열의 정보를 입력 받고, tree 벡터의 사이즈를 4 * n만큼으로 초기화 해주고 build 해준다.
2. m개의 쿼리를 받아준다, 업데이트 관련 쿼리인 경우 uq 큐에 변경할 인덱스와 값을 추가해 준다.
3. 질의 관련 쿼리인 경우 튜플을 통해 업데이트 순번, 시작, 종료 인덱스, 쿼리의 질문 순서를 4개 사이즈의 tuple형태로 temps 벡터에 추가해 준다.
4. temps 벡터를 업데이트 순번을 기준 오름차순 정렬해 준 뒤 qq 큐에 순서대로 추가해 준다.
5. solution 함수에서 update 및 query에 대한 내용을 처리해 준다.
6. 초기 업데이트 순번uds는 0으로 시작하고 uq와 qq가 모두 빌때까지 while루프를 실행해 준다.
7. 업데이트 순번이 0인 쿼리부터 모두 실행해 준다, 이때 쿼리가 들어온 질문 순서에 따라 ans 배열의 인덱스에 지정하여 쿼리 결과를 저장해 준다. 업데이트 순번이 0인 쿼리를 모두 실행했다면 break 해준다.
8. uq 큐가 모두 빈 상태가 아니라면 업데이트를 한번 진행해 주고 uds 를 1올려준다.
9. 다음 루프에서는 uds가 1인 즉, 업데이트 순번이 1인 쿼리에 대한 내용을 쭉 진행한다.
10. 업데이트 순번이 1인 쿼리가 모두 진행되었을 경우 추가로 업데이트를 진행해주고 uds를 1올 올려준다.
11. 7 ~ 10번에 해당하는 작업을 uq, qq가 모두 빌 때까지 진행해 준다.
12. ans에 저장된 쿼리의 결과를 질의 순서에 따라 출력해 주면 된다.

 

참고 사항

업데이트 순번을 따라서만 정렬을 해줘야 한다, 아니면 이후 쿼리에 대해 순서가 섞일 수 있다.

최악의 케이스를 보면 쿼리의 출력 값이 100만 * 10만으로 int 타입의 범위를 벗어날 수 있으므로 tree와 query 함수 내 정수형 타입을 long long으로 해주어야 한다.

 

정답 코드

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

struct updates {
	int index, value;
};

vector<long long> tree;
queue<updates> uq;
queue<tuple<int, int, int, int>> qq;
int n, m;
long long ans[1000001] = { 0 };

void build(vector<int>& lst, int node, int start, int end) {
	if (start == end) tree[node] = lst[start];
	else {
		int mid = (start + end) / 2;
		build(lst, node * 2, start, mid);
		build(lst, node * 2 + 1, mid + 1, end);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

void update(int node, int start, int end, int idx, int val) {
	if (start == end) tree[node] = val;
	else {
		int mid = (start + end) / 2;
		if (start <= idx && idx <= mid) update(node * 2, start, mid, idx, val);
		else update(node * 2 + 1, mid + 1, end, idx, val);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

long long query(int node, int start, int end, int L, int R) {
	if (R < start || end < L) return 0;
	if (L <= start && end <= R) return tree[node];
	int mid = (start + end) / 2;
	long long left = query(node * 2, start, mid, L, R);
	long long right = query(node * 2 + 1, mid + 1, end, L, R);
	return left + right;
}

void solution() {
	int uds = 0;
	while (!uq.empty() || !qq.empty()) {
		while (!qq.empty()) {
			tuple<int, int, int, int> qr = qq.front();
			int uid = get<0>(qr), start = get<1>(qr), end = get<2>(qr), qindex = get<3>(qr);
			if (uid != uds) break;
			qq.pop();
			ans[qindex] = query(1, 0, n - 1, start - 1, end - 1);
		}
		if (!uq.empty()) {
			updates ud = uq.front(); uq.pop();
			update(1, 0, n - 1, ud.index - 1, ud.value);
			uds++;
		}
	}
}

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

	cin >> n;
	vector<int> lst(n);
	tree.resize(4 * n);
	for (int i = 0; i < n; i++) cin >> lst[i];
	build(lst, 1, 0, n - 1);

	cin >> m;
	int qrs = 0;
	vector<tuple<int, int, int, int>> temps;
	while (m--) {
		int order;
		cin >> order;
		if (order == 1) {
			int idx, val;
			cin >> idx >> val;
			uq.push({ idx, val });
		}
		else {
			int uid, start, end;
			cin >> uid >> start >> end;
			temps.push_back({ uid, start, end, qrs++ });
		}
	}
	sort(temps.begin(), temps.end(), [](const tuple<int, int, int, int>& a, const tuple<int, int, int, int>& b) {return get<0>(a) < get<0>(b); });
	for (int i = 0; i < qrs; i++) qq.push(temps[i]);
	solution();
	for (int i = 0; i < qrs; i++) {
		cout << ans[i] << "\n";
	}
}