[P5] 백준 27897번 특별한 화재 경보 C++ 세그먼트 트리

리뷰

 

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

L값의 범위를 보고 살짝 당황했는데 N의 범위를 보고 풀이가 가능하다는 것을 깨달은 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• tree : 구간 합 세그먼트 트리 정보를 저장할 배열
• n : 배열의 크기를 저장할 변수
• h : 각 학생의 키를 저장할 변수
• l : 인접한 두 학생을 바꿀 수 있는 횟수를 저장할 변수

 

함수

1. query

int query(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	return query(node * 2, s, mid, L, R) + query(node * 2 + 1, mid + 1, e, L, R);
}

 

세그먼트 트리의 L~R번 노드 구간의 합을 구하기 위한 함수

 

2. update

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

 

세그먼트 트리 리프 노드를 증가시키고, 상위 노드값을 업데이트하기 위한 함수

 

 

문제풀이

1. n, l값을 입력 받고, 변수 a를 0으로 초기화한다.
2. n개의 키 정보를 h에 입력 받고, query함수를 통해 세그먼트 트리에서 h+1~n번 구간합을 a에 더해준다.
3. update함수를 통해 세그먼트 트리의 h번 인덱스를 증가시키고, 업데이트 처리한다.
4. a + l과 n*(n-1)/2 중 더 작은 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. l이 최대 10^18이므로 l, a값을 long long타입으로 지정해주어야한다.
2. n이 최대 50만이므로 n*(n-1)/2앞에 1ll을 곱해 주어야 long long타입으로 변환된다.
3. 그 외 변수들은 int형으로 지정하여도 오버플로우가 발생하지 않는다.

 

정답 코드

#include<iostream>
using namespace std;
using ll = long long;

const int N = 5e5 + 1;
int tree[N * 4];
int n, h;
ll l;

int query(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	return query(node * 2, s, mid, L, R) + query(node * 2 + 1, mid + 1, e, L, R);
}

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

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

	cin >> n >> l;	
	ll a = 0;
	for (int i = 0; i < n; ++i) {
		cin >> h;
		a += query(1, 1, n, h + 1, n);
		update(1, 1, n, h);
	}
	cout << min(a + l, 1ll * n * (n - 1) / 2);
}