[C/C++] 백준 - 머지 소트 트리 문제

 

 

머지 소트 트리(Merge Sort Tree)는 트리의 일종으로 merge sort과정을 그대로 트리 모양으로 접합시킨 트리

트리의 높이는 log N 정도이고, 하나의 층에 총 N개의 원소가 있으므로

공간복잡도 역시 O(N log N)수준

구현이 문제인데, 이것은 merge 함수를 이용하여 생각보다 간단하게 구현이 가능

 

 

백준 13537번 수열과 쿼리 1

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

13537번: 수열과 쿼리 1

 

    각 배열들을 병합하는 과정이 소요되고 그때 배열의 크기가 확장되기 때문에

     v[node]의 크기를 합치는 두 배열의 크기의 합으로 재설정(v[node*2].size()+v[node*2+1).size())

     병합 과정은 c++에서 제공하는 merge함수로 구현

     나머지 부분은 기존의 세그먼트 트리와 거의 유사하고 k보다 큰 원소의 개수를 출력하는 부분

     => return v[node].end() - upper_bound(v[node].begin(), v[node].end(), x)를 사용하였는데 

     upper_bound는 어떤 원소보다 큰 원소의 인덱스를 출력해준다는 점

     자세한 것은 아래 코드 보기

 

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

struct mergeSortTree { // 구조체를 만들어서 간편하게 사용하기
	vector<vector<int>>v;

	void init(int node, int start, int end, vector<int>& u) {
		if (start == end) {
			v[node].push_back(u[start - 1]);
			return;
		}

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

		v[node].resize(v[node * 2].size() + v[node * 2 + 1].size()); 
		merge(v[node * 2].begin(), v[node * 2].end(), v[node * 2 + 1].begin(), v[node * 2 + 1].end(), v[node].begin());
	}

	int gt(int node, int start, int end, int l, int r, int x) {
		if (r<start || l>end)
			return 0;
		if (l <= start && end <= r)
			return v[node].end() - upper_bound(v[node].begin(), v[node].end(), x);
		int mid = (start + end) / 2;
		return gt(node * 2, start, mid, l, r, x) + gt(node * 2 + 1, mid + 1, end, l, r, x);
	}

};
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	mergeSortTree f;
	f.v.resize(1 << 18);

	int N,M;
	cin >> N;

	vector<int>v(N);
	for (int i = 0; i < N; i++)
		cin >> v[i];

	f.init(1, 1, N, v);
	cin >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		int ans = f.gt(1, 1, N, a, b, c);
		cout << ans << '\n';
	}
}

 

 

백준 13544번 수열과 쿼리 3

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

13544번: 수열과 쿼리 3

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

int ans;
struct mergeSortTree {
	vector<vector<int>>v;
	void init(int node, int start, int end, vector<int>& u) {
		if (start == end) {
			v[node].push_back(u[start - 1]);
			return;
		}
		int mid = (start + end) / 2;
		init(node * 2, start, mid, u);
		init(node * 2 + 1, mid + 1, end, u);

		v[node].resize(v[node * 2].size() + v[node * 2 + 1].size());
		merge(v[node * 2].begin(), v[node * 2].end(), v[node * 2 + 1].begin(), v[node * 2 + 1].end(), v[node].begin());
	}
	
	int gt(int node, int start, int end, int l, int r, int x) {
		if (end<l || start>r)
			return 0;
		if (l <= start && end <= r)
			return v[node].end() - upper_bound(v[node].begin(), v[node].end(), x);
		int mid = (start + end) / 2;
		return gt(node * 2, start, mid, l, r, x) + gt(node * 2 + 1, mid + 1, end, l, r, x);
	}

};
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	mergeSortTree f;
	f.v.resize(1 << 18);
	int N, M;
	cin >> N;

	vector<int>v(N);
	for (int i = 0; i < N; i++)
		cin >> v[i];
	f.init(1, 1, N, v);

	cin >> M;
	
	for (int i = 0; i < M; i++) {
		int a, b, c;
 		cin >> a >> b >> c;
		if(i==0)
			ans = f.gt(1, 1, N, a, b, c);
		else
		{
			a ^= ans;
			b ^= ans;
			c ^= ans;
			ans = f.gt(1, 1, N, a, b, c);

		}
		cout << ans << '\n';

	}
}