BOJ 14170 - Counting Haybales (usaco silver, 차원압축, 세그먼트트리)

 

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

 

분류를 차원압축과 세그먼트트리로 하긴 했지만 훨씬 쉽게 풀 수는 있다.

 

하지만, 차원압축에 익숙해지기 위한 예제로 사용하면 좋을 것 같다.

 

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <set>
using namespace std;
const int MAX = 1 << 18;

int arr[MAX];

void construct() {
	for (int i = MAX / 2 - 1; i >= 1; i--)
		arr[i] = arr[i * 2] + arr[i * 2 + 1];
}

int sum(int s, int e, int node, int ns, int ne) {
	if (e < ns || ne < s) return 0;
	if (s <= ns && ne <= e) return arr[node];
	int mid = (ns + ne) / 2;
	return sum(s, e, node * 2, ns, mid) + sum(s, e, node * 2 + 1, mid + 1, ne);
}
int sum(int s, int e) {	return sum(s, e, 1, 0, MAX/2 - 1);}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, q; cin >> n >> q;

	int x[100000], hsize=0;
	set<int> xSet;
	unordered_map<int, int> xHash;

	//입력 및 차원압축
	for (int i = 0,input; i < n; i++) {
		cin >> x[i];
		xSet.insert(x[i]);
	}
	sort(x, x + n);
	for (int x : xSet) 
		xHash[x] = hsize++;

	//차원압축된 것을 바탕으로 세그먼트 트리 채우기
	for (int i = 0; i < n; i++)
		arr[MAX / 2 + xHash[x[i]]] = 1;
	
	construct();

	//차원압축된 좌표에 맞게 쿼리에 주어진 a,b도 조정한 후 sum호출
	for (int i = 0,a,b; i < q; i++) {
		cin >> a >> b;
		auto it1 = lower_bound(x, x+ n, a);
		auto it2 = upper_bound(x, x+n, b);
		if (it1 == x + n) {
			cout << 0 << '\n';
			continue;
		}
		a = xHash[*it1];
		b = xHash[*(it2-1)];
		cout << sum(a, b) << '\n';
	}
	
}

 

 

 

아래는 백준에서 isvara님의 코드를 복붙했습니다.

입력을 배열에 저장하고 오름차순 정렬하면 index를 기준으로 구간에 몇개의 haybale이 있는지 구할 수 있다.

const int max_n = 1e5 + 1;

int N, Q;
int coor[max_n];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> Q;
	for (int i = 0; i < N; i++)
		cin >> coor[i];
	coor[N] = 1000000001;
	sort(coor, coor + N);
	for (int i = 0; i < Q; i++)
	{
		int l, r;
		cin >> l >> r;

		auto lt=lower_bound(coor, coor + N, l);
		auto rt = lower_bound(coor, coor + N, r+1);
	 
		cout << (rt - lt)<<"\n";
	}
}