BOJ_24506 blobpopcorn (C++)

↑클릭 시 문제로 이동

개요

블롭컵 당시 딱 봐도 세그먼트 트리/인덱스 트리 문제여서 쉽게 풀 수 있지 않을까 하고 시도했다가 멸망해버린 그 문제. 😅 물론 못 풀고 대회 중에 맞은 사람이 아무도 없어서 포기할까 싶었으나 “시도했으나 맞지 못한 문제” 태그에 남아있는 게 거슬려서 5일동안 시도해서 겨우 풀었다.

처음 분류가 책정됐을 때에 느리게 갱신되는 세그먼트 트리도 붙어있었는데 나도 그렇게 풀지 않았고 얼마 안 지나서 분류 태그에서 사라진 거 보니 필수는 아닌 듯 하다.

풀이는 블롭컵 주최 측에서 올려주신 해설을 참고했다. 해설을 아무리 읽어도 처음엔 구현이 너무 힘들었지만…

---

쌍의 개수

대회를 볼 때 생각한 건 당연히 TLE가 나올 줄 알고 있었고 실제로도 TLE가 난 방법으로 모든 블롭 쌍에 대해서 그 사이에 있는 블롭들의 최대 높이를 인덱스 트리로 구해 비교하는 $O(Q\cdot N^2lgN)$의 말도 안 되는 시간복잡도를 가진 방법이다.

당연히 실패하고 해설이 올라오기 전까지 나름 계속 고민했을 땐 트리가 update될 때 쌍의 개수도 업데이트하는 방법이어야 되겠다는 생각과 각 블롭을 기준으로 좌우에 있는 블롭들을 확인하면 되지 않을까 하는 모호한 아이디어를 떠올렸다.

해설을 천천히 읽어보고 정리한 쌍의 개수를 구하는 방법은 다음과 같다.

lx와 rx 정의

• x번째 블롭에서 왼쪽으로 이동할 때 x보다 큰 블롭이 처음 나오는 위치를 lx, 오른쪽으로 이동할 때 x보다 큰 블롭이 처음 나오는 위치를 rx라 하자.
• lx와 x, rx와 x는 둘 사이의 블롭들을 구경할 수 있다.
• 블롭 x와 블롭 y가 사이의 블롭들을 구경할 수 있고 A[x] < A[y] 이면 y는 lx이거나 rx여야 한다.

전체 개수 정의

• 조건에 맞는 쌍을 [키가 작은 블롭, 키가 큰 블롭]으로 생각하면 각각 블롭이 키가 작은 블롭이 되는 쌍은 최대 두 개이므로 전체 쌍의 개수의 최댓값은 2N이다.
• x번째 블롭이 키가 작은 블롭이 되는 쌍이 두 개보다 작은 경우는 lx가 존재하지 않거나 rx가 존재하지 않는 경우이다.
• 결국 전체 개수는 모든 x에 대해 lx가 존재하지 않는 x의 개수 wl과 rx가 존재하지 않는 x의 개수 wr을 세면 된다.
• 그러므로 답은 2N - wl - wr이다.

w 구하기

• 먼저 lx가 존재하지 않는 x의 개수를 센다.
• l1은 존재하지 않는다.
• A[x]를 확인하며 A[1] ~ A[x]의 최댓값이 A[x]인 경우 lx는 존재하지 않는다. (자기보다 큰 블롭이 없으므로)
• 이러한 lx가 존재하지 않는 x에 대해 A[x]를 나열하면 증가수열이다. 이 증가수열의 길이가 wl이다.
• wr도 똑같은 방법으로 구한다. (나는 A[x]를 역순으로 저장한 인덱스 트리를 하나 더 만들어서 구함)

위의 내용을 인덱스 트리로 구현하였다.

---

인덱스 트리

평소에 LIS 문제를 인덱스 트리로 연습도 해보았기에 호기롭게 시작했으나 구현이 너무 어려웠다.
사실 지금까지 모든 세그먼트 트리 문제를 인덱스 트리로 풀어온 바텀업에 익숙한 나는 탑다운 재귀 방식이 필수적인 이 문제가 어려운 것은 당연한 것일지도 모르겠다.

아무튼 이 문제의 트리 핵심은 두 증가 수열을 합칠 때, 왼쪽 증가 수열의 길이가 s이고 왼쪽 증가 수열의 마지막 원소보다 큰 원소가 오른쪽 증가 수열에 k개 있을 때 합친 증가 수열의 길이는 (s+k)라는 점이다.

시간복잡도

이렇게 증가 수열의 길이 a와 증가수열의 최댓값 v를 저장하는 인덱스 트리를 구성하면 A[i]가 변할 경우, 노드 lg N개의 정보가 변경되고, 각각의 노드에서 자식 노드들을 합칠 때에는 오른쪽 자식 노드의 a와 v를 재귀적으로 확인해야 하므로 $O(lgN)$이 걸린다. 즉 1번 질의로 A[i]가 변했을 때 트리를 갱신하는 데에는 $O(lg^2N)$이 걸린다. 전체 증가 수열의 길이는 루트 노드의 a값과 같으므로 $O(1)$로 구할 수 있고, 이를 lx, rx에 대해 두번 시행하면 된다.
전처리에 $O(Nlg^2N)$, 1번 질의에 $O(lg^2N)$, 2번 질의에 $O(1)$이 필요하므로 전체적인 시간복잡도는 $O((N+Q)lg^2N)$이다. 😲

count 하기

원리를 이해는 했지만 사실 왼쪽 증가 수열의 마지막 원소보다 큰 원소가 오른쪽 증가 수열에 몇개 있는 지 세는 것이 상당히… 어려웠다.
처음엔 단순하게 오른쪽 서브트리의 모든 노드를 하나하나 확인하며 비교했으나 시간 역시 문제지만 현재 확인하고 있는 노드가 오른쪽 증가 수열에 포함되고 있는 노드인지 아닌지 판별이 불가능했다. (3일 날렸다)
즉 단순히 대소비교를 할 것이 아닌 오른쪽 트리에서 증가 수열에 포함되고 있는 A에 대해서만 비교해 개수를 세어야 한다는 게 핵심이었다.

정말 수많은 시행착오 끝에 결과 코드는 처음보다 간결해졌는데 count 함수에 대해 수도 코드를 작성해보면 다음과 같다.

count(node, L_max){ // L_max is left lis' maxv
    if (node.a == 1) { // stop recursion
        return (node.v > L_max) ? 1 : 0; 
    }
    if (left_child.v > L_max) { // left child of node
        // if left_child's maxv > L_max,
        // every right_child's maxv > L_max
        cnt = node.a - left_child.a;
        return cnt + count(left_child, L_max);
    }
    else {
        // ignore left_child
        return count(right_child, L_max);
    }
}

자식 노드들을 한칸 한칸 내려오며 왼쪽을 선택할 지 오른쪽을 선택할 지만 판별해주고, 만약 왼쪽 자식 노드의 v가 기준 v보다 커서 왼쪽을 선택할 경우 현재 노드의 수열의 길이에서 왼쪽 자식 노드의 수열의 길이를 빼준만큼 더해서 재귀를 진행한다. 오른쪽 증가 수열에서 왼쪽 증가 수열의 최댓값보다 큰 원소들은 당연히 기준 v보다 클 것이기 때문이다. (단순히 오른쪽 증가 수열의 길이를 더해주면 안된다. 오른쪽 증가 수열의 원소들은 왼쪽 증가 수열의 최댓값보다 크다는 보장이 없기 때문이다.)
반대로 왼쪽 자식 노드의 v가 기준 v보다 작다면 왼쪽 트리는 무시한다.

---

결론

푸는 5일간은 정말 미친 듯이 어려웠는데 막상 해결하고 나니 전체적인 구현 자체는 생각보다 간단한 느낌이 든다. (코드는 그렇지 못하다…)
하지만 역시 문제에서 요구하는 시간복잡도에 맞춰 설계하기가 상당히 어려웠고 구현한 후에도 맞왜틀 때문에 결국 감사하게도 검수자분이 반례를 알려주셔서 해결할 수 있었다. 물론 반례를 고치면서 위에 언급한 모든 노드를 스캔하는 문제도 동시에 해결해야 했다.
얻은 교훈은 못 풀 것 같은 문제는 절대 제출도 하지말라… 😑

---

코드

/* BOJ_24506 blobpopcorn */
/* hanabzu */

#include <iostream>
#include <algorithm>
#include <utility>

using namespace std;

const int MAXN = 100000;
const int POWN = 18;
int N, Q, B, q, x, y, m;

pair<int, int> w_l[1 << POWN]; // lx가 존재하지 않는 x의 개수 LIS
pair<int, int> w_r[1 << POWN]; // rx가 존재하지 않는 x의 개수 LIS

void init();
void update(int p, int c);
int count_num(int p, pair<int, int>(&w)[1 << POWN]);

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

	cin >> N >> Q;

	for (B = 1; B < N; B <<= 1);

	for (int i = B; i < B + N; i++) {
		cin >> w_l[i].first;
		w_l[i].second = 1;
		w_r[(B << 1) + N - i - 1] = w_l[i];
	}

	init();
	
	while (Q--) {
		cin >> q;
		if (q == 1) {
			cin >> x >> y;
			update(x, y);
		}
		else {
			cout << (N << 1) - w_l[1].second - w_r[1].second << '\n';
		}
	}
	return 0;
}

void init() {
	for (int i = B - 1; i > 0; i--) {
		if (w_l[i << 1].first < w_l[(i << 1) | 1].first) {
			w_l[i] = w_l[(i << 1) | 1];
			m = w_l[i << 1].first;
			w_l[i].second = w_l[i << 1].second + count_num((i << 1) | 1, w_l);
		}
		else {
			w_l[i] = w_l[i << 1];
		}

		if (w_r[i << 1].first < w_r[(i << 1) | 1].first) {
			w_r[i] = w_r[(i << 1) | 1];
			m = w_r[i << 1].first;
			w_r[i].second = w_r[i << 1].second + count_num((i << 1) | 1, w_r);
		}
		else {
			w_r[i] = w_r[i << 1];
		}
	}
}

void update(int p, int c) {
	int lp = p + B - 1;
	int rp = B + N - p;

	w_l[lp].first = w_r[rp].first = c;

	while (lp >>= 1) {
		if (w_l[lp << 1].first < w_l[(lp << 1) | 1].first) {
			w_l[lp] = w_l[(lp << 1) | 1];
			m = w_l[lp << 1].first;
			w_l[lp].second = w_l[lp << 1].second + count_num((lp << 1) | 1, w_l);
		}
		else {
			w_l[lp] = w_l[lp << 1];
		}
	}

	while (rp >>= 1) {
		if (w_r[rp << 1].first < w_r[(rp << 1) | 1].first) {
			w_r[rp] = w_r[(rp << 1) | 1];
			m = w_r[rp << 1].first;
			w_r[rp].second = w_r[rp << 1].second + count_num((rp << 1) | 1, w_r);
		}
		else {
			w_r[rp] = w_r[rp << 1];
		}
	}
}

int count_num(int p, pair<int, int>(&w)[1 << POWN]) {
	int cnt;
	if (w[p].second == 1) {
		return (w[p].first > m) ? 1 : 0;
	}
	if (w[p << 1].first > m) {
		cnt = w[p].second - w[p << 1].second;
		return cnt + count_num(p << 1,  w);
	}
	else { // w[p << 1].first < m
		return count_num((p << 1)|1, w);
	}
}

---

오타 수정, 알고리즘 질문 등은 댓글로 남겨주세요. 감사합니다. 😹