백준 13544 수열과 쿼리 3 (c++) : 피너클

13544번: 수열과 쿼리 3

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

 

세그먼트 트리는 참 변형된게 많다.

여기서는 머지소트트리를 이용한다.

 

위에가 세그먼트 트리고 아래가 머지 소트 트리다.

가장 큰 차이점은 숫자를 정렬한다는 것이다.

세그먼트 트리는 그 자리 그대로 사용하지만 머지 소트 트리는 숫자를 정렬한다. merge sort와 동일하게 생각하면 된다.

 

int n, m;
int arr[100001];
vector<int> segtree[4 * 100001];

사용할 변수들이다.

segtree에는 당연히 범위 안의 숫자들이 정렬된 상태로 들어갈 것이다.

void init(int node, int start, int end, int left, int right) {
	if (end < left || right < start) return;
	if (start == end) {
		segtree[node].push_back(arr[start]);
		return;
	}
	int mid = (start + end) / 2;
	init(node * 2, start, mid, left, right);
	init(node * 2 + 1, mid + 1, end, left, right);

	int l = segtree[node * 2].size();
	int r = segtree[node * 2 + 1].size();
	int i = 0, j = 0;

	while (i < l && j < r) {
		if (segtree[node * 2][i] < segtree[node * 2 + 1][j]) {
			segtree[node].push_back(segtree[node * 2][i]);
			i++;
		}
		else {
			segtree[node].push_back(segtree[node * 2 + 1][j]);
			j++;
		}
	}
	while (i < l) {
		segtree[node].push_back(segtree[node * 2][i]);
		i++;
	}
	while (j < r) {
		segtree[node].push_back(segtree[node * 2 + 1][j]);
		j++;
	}
	return;
}

초기화 함수다.

	if (end < left || right < start) return;
	if (start == end) {
		segtree[node].push_back(arr[start]);
		return;
	}

기본 처리를 해주고

	int mid = (start + end) / 2;
	init(node * 2, start, mid, left, right);
	init(node * 2 + 1, mid + 1, end, left, right);

	int l = segtree[node * 2].size();
	int r = segtree[node * 2 + 1].size();
	int i = 0, j = 0;

자식 머지소트트리를 준비해준다음

	while (i < l && j < r) {
		if (segtree[node * 2][i] < segtree[node * 2 + 1][j]) {
			segtree[node].push_back(segtree[node * 2][i]);
			i++;
		}
		else {
			segtree[node].push_back(segtree[node * 2 + 1][j]);
			j++;
		}
	}
	while (i < l) {
		segtree[node].push_back(segtree[node * 2][i]);
		i++;
	}
	while (j < r) {
		segtree[node].push_back(segtree[node * 2 + 1][j]);
		j++;
	}
	return;
}

자기 자신에게 작은 순으로 넣어주면 된다.

int query(int node, int start, int end, int left, int right, int k) {
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) {
		auto it = upper_bound(segtree[node].begin(), segtree[node].end(), k);
		return segtree[node].end() - it;
	}

	int mid = (start + end) / 2;
	return query(node * 2, start, mid, left, right, k) + query(node * 2 + 1, mid + 1, end, left, right, k);
}

쿼리다.

upper_bound로 k보다 큰 숫자의 위치를 찾는다.

그리고 그 크기를 반환하면 끝이다.

	cin >> n;
	for (int i = 1; i <= n; i++) cin >> arr[i];

	init(1, 1, n, 1, n);

	cin >> m;
	int last_ans = 0;
	while (m-- > 0) {
		int a, b, c;
		cin >> a >> b >> c;
		int i = a ^ last_ans;
		int j = b ^ last_ans;
		int k = c ^ last_ans;
	
		last_ans = query(1, 1, n, i, j, k);

		cout << last_ans << '\n';
	}

그 위에는 입력하는 부분들이다.

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

using namespace std;

int n, m;
int arr[100001];
vector<int> segtree[4 * 100001];

void init(int node, int start, int end, int left, int right) {
	if (end < left || right < start) return;
	if (start == end) {
		segtree[node].push_back(arr[start]);
		return;
	}
	int mid = (start + end) / 2;
	init(node * 2, start, mid, left, right);
	init(node * 2 + 1, mid + 1, end, left, right);

	int l = segtree[node * 2].size();
	int r = segtree[node * 2 + 1].size();
	int i = 0, j = 0;

	while (i < l && j < r) {
		if (segtree[node * 2][i] < segtree[node * 2 + 1][j]) {
			segtree[node].push_back(segtree[node * 2][i]);
			i++;
		}
		else {
			segtree[node].push_back(segtree[node * 2 + 1][j]);
			j++;
		}
	}
	while (i < l) {
		segtree[node].push_back(segtree[node * 2][i]);
		i++;
	}
	while (j < r) {
		segtree[node].push_back(segtree[node * 2 + 1][j]);
		j++;
	}
	return;
}

int query(int node, int start, int end, int left, int right, int k) {
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) {
		auto it = upper_bound(segtree[node].begin(), segtree[node].end(), k);
		return segtree[node].end() - it;
	}

	int mid = (start + end) / 2;
	return query(node * 2, start, mid, left, right, k) + query(node * 2 + 1, mid + 1, end, left, right, k);
}

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; i++) cin >> arr[i];

	init(1, 1, n, 1, n);

	cin >> m;
	int last_ans = 0;
	while (m-- > 0) {
		int a, b, c;
		cin >> a >> b >> c;
		int i = a ^ last_ans;
		int j = b ^ last_ans;
		int k = c ^ last_ans;
	
		last_ans = query(1, 1, n, i, j, k);

		cout << last_ans << '\n';
	}

	return 0;
}

전체코드다.