BOJ 32383 점프

문제 링크입니다.

코스트가 제곱임에 주목하자

일반성을 잃지 않고 $H_a > H_b > H_c$라고 합시다.

$D_{ab} = H_a-H_b, D_{bc} = H_b-H_c$라고 하면,

$(D_{ab}+D_{bc})^2 = D_{ab}^2 + D_{bc}^2 +2D_{ab}D{bc} > D_{ab}^2 + D_{bc}^2$입니다.

한 빌딩에서 다른 빌딩까지 가는 경로를 쪼갤 수 있다면 쪼개는 것이 유리합니다.

(아래로 가야 하는데 위로 가도록 경로를 쪼개는 것은 당연히 배제합니다.)

높은 빌딩을 넘어갈 수 없다

가장 높은 빌딩 $X$를 생각합시다. $X$를 기준으로 빌딩은 두 그룹으로 나뉘어, 다른 그룹으로 넘어가기 위해서는 반드시 $X$를 거쳐야 합니다. 또 나뉜 그룹들 안에서도 가장 큰 빌딩을 찾아 두 그룹으로 나누고, 나누고, 나누면…

데카르트 트리가 만들어집니다. 이제 문제를 트리 DP로 환원할 수 있습니다.

각 서브트리에, 해당 서브트리 안에서 루트로 가는 거리의 합을 저장합니다.

경로는 트리의 최소 공통 조상을 거쳤다가 내려가는 형태가 되기 때문에, 전체 트리에서의 거리 합은 각 서브트리마다 그 서브트리의 루트를 거치는 경로들을 더하면 됩니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll mod = 1e9+7;

ll ans; int n;
ll h[505050], d[505050];
int tree[4040404];

void init(int now, int l, int r){
	if(l == r){
		tree[now] = l;
		return;
	}
	int mid = l+r>>1;
	init(now<<1, l, mid);
	init(now<<1|1, mid+1, r);
	tree[now] = (h[tree[now<<1]] > h[tree[now<<1|1]]) ? tree[now<<1] : tree[now<<1|1];
}

int qry(int now, int l, int r, int L, int R){
	if(l > R || L > r) return 0;
	if(L <= l && r <= R) return tree[now];
	int mid = l+r>>1;
	int lt = qry(now<<1, l, mid, L, R);
	int rt = qry(now<<1|1, mid+1, r, L, R);
	if(!lt) return rt;
	if(!rt) return lt;
	return h[lt] > h[rt] ? lt : rt;
}

int solve(int l, int r){
	if(l > r) return 0;
	if(l == r) return l;
	
	int mx = qry(1, 1, n, l, r);
	int lt = solve(l, mx-1);
	int rt = solve(mx+1, r);
	
	d[mx] = 0;
	if(lt) d[mx] += ((h[mx]-h[lt])*(h[mx]-h[lt])%mod*(mx-l)%mod+d[lt])%mod;
	d[mx] %= mod;
	if(rt) d[mx] += ((h[mx]-h[rt])*(h[mx]-h[rt])%mod*(r-mx)%mod+d[rt])%mod;
	d[mx] %= mod;
	ans = (ans+d[mx])%mod;
	
	if(lt && rt){
		ans += (mx-l)%mod*(r-mx)%mod*(((h[mx]-h[lt])*(h[mx]-h[lt])%mod+(h[mx]-h[rt])*(h[mx]-h[rt])%mod)%mod)%mod; ans %= mod;
		ans += (mx-l)%mod*d[rt]%mod; ans %= mod;
		ans += (r-mx)%mod*d[lt]%mod; ans %= mod;
	}
	return mx;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	cin >> n; for(int i = 1; i <= n; i++) cin >> h[i];
	init(1, 1, n); solve(1, n); cout << ans;
}