[KTSC 2019] 외계 선인장

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

 

문제 컨셉이 심플하니 예쁘게 생겼길래 붙잡고서 친구랑 뻘소리 좀 주고 받으면서 20분 쳐다보니 떠올랐다.

2년 전에 풀었던 APIO - 2021 밀림 점프(https://mathsciforstudent.tistory.com/376)의 하위 호환 문제였다.

저 문제는 자력솔은 못했지만 정말 재밌게 풀었던 문제라 잊을래야 잊을 수 없다.

 

히스토그램에서 자기보다 높아지는 첫 인덱스와 간선을 연결하는 식으로 트리를 구성할 수 있다.

이걸 카르테시안 트리라고 부르는 것 같던데, 뭔지 모르기 때문에 그냥 히스토그램 트리라고 하겠다.

 

히스토그램 트리에서 업데이트가 없고, 점프를 뛸 때마다 히스토그램에서 먹고 들어가는 각각의 부분 직사각형이 고정되므로.. 스파스 테이블 네 개를 들고 처리하면 풀 수 있다.

 

S에서 E쪽으로 뛰면서 부분 직사각형 합하기 + E쪽에서 S쪽으로 뛰면서 부분 직사각형 합하기

 

+) 원래는 다 long long 써서 이런걸로 안 틀리는데.. 인풋들이 int라서 int 쓰다가 그새 오버플로우 실수로 두 번 틀렸다. 무조건 long long을 쓸 것.

+) n = size(_H)가 아니라 n = size(H)를 했다가 자꾸 n=500003이 들어오면서 터져서 찾느라 고생했다. 흠....

 

#include "cactus.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 5e5 + 3;
int n;

struct Jump {
	int next;
	ll value;
};

Jump L[N][20];
Jump R[N][20];
ll H[N], p[N];

void init(vector<int> _H){
	n = size(_H);
	
	for(int i=1; i<=n; ++i) {
		H[i] = _H[i-1];
		p[i] = p[i-1] + H[i];
	}
	
	H[0] = H[n+1] = 1e9 + 1;
	
	L[n+1][0].next = n+1;
	R[0][0].next = 0;
	
	vector<int> stk;
	for(int i=1; i<=n+1; ++i) {
		while (!empty(stk) && H[stk.back()] < H[i]) {
			L[stk.back()][0].next = i;
			L[stk.back()][0].value = ll(i-stk.back()) * H[stk.back()];
			stk.pop_back();
		}
		stk.push_back(i);
	}
	stk.clear();
	for(int i=n; i>=0; --i) {
		while (!empty(stk) && H[stk.back()] < H[i]) {
			R[stk.back()][0].next = i;
			R[stk.back()][0].value = ll(stk.back()-i) * H[stk.back()];
			stk.pop_back();
		}
		stk.push_back(i);
	}
	
	for(int d=1; d<20; ++d) {
		for(int i=0, j; i<=n+1; ++i) {
			j=L[i][d-1].next;
			L[i][d].next = L[j][d-1].next;
			L[i][d].value = L[i][d-1].value + L[j][d-1].value;
			
			j=R[i][d-1].next;
			R[i][d].next = R[j][d-1].next;
			R[i][d].value = R[i][d-1].value + R[j][d-1].value;
		}
	}
}

ll query(int S, int E){
	ll ans = - p[E] + p[S-1];
	
	for(int d=19; d>=0; --d) {
		if(L[S][d].next <= E) {
			ans += L[S][d].value;
			S = L[S][d].next;
		}
	}
	
	for(int d=19; d>=0; --d) {
		if(R[E][d].next >= S) {
			ans += R[E][d].value;
			E = R[E][d].next;
		}
	}
	
	assert(H[S] == H[E]);
	
	ans += ll(E-S+1) * H[S];
	
	return ans;
}