간단하고 짧고 범용성 있는 Li-Chao Tree

13263 나무 자르기.cpp

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int MXN=1e5;

int A[MXN], B[MXN], N;
ll D[MXN];
ll f(int j, int i) { return D[j] + 1LL*A[i]*B[j]; }
bool cmp(int i, int j, int x) { return f(i, x)<f(j, x); }

struct node { int v, l, r; } T[MXN];
int id=1;
void add(int a) {
	int s=1, e=N-1, i=1;
	while(i) {
		int m=s+e>>1, &b=T[i].v;
		if(cmp(a, b, m)) swap(a, b);
		if(cmp(a, b, s)) e=m-1, i=T[i].l=T[i].l?:++id;
		else if(cmp(a, b, e)) s=m+1, i=T[i].r=T[i].r?:++id;
		else break;
	}
}
int qry(int x) {
	int s=1, e=N-1, i=1, a=0;
	while(i) {
		int m=s+e>>1, b=T[i].v;
		if(cmp(b, a, x)) a=b;
		if(x<m) e=m-1, i=T[i].l;
		else if(x>m) s=m+1, i=T[i].r;
		else break;
	}
	return a;
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>N;
	for(int i=0; i<N; i++) cin>>A[i];
	for(int i=0; i<N; i++) cin>>B[i];

	for(int i=1; i<N; i++) {
		add(i-1);
		D[i]=f(qry(i), i);
	}
	cout<<D[N-1];
}

설명

• 리차오 트리는 함수의 배열을 관리하는 세그먼트 트리이다.
  • 일차함수(직선)은 아래 조건을 만족하기 때문에 흔히 '직선을 관리하는 자료구조'라 알려져 있으나, 조건만 만족한다면 직선일 필요는 없다.
• 배열에서 i≠j에 대해 i번째 함수와 j번째 함수가 둘 이상의 교점을 가지지 않는 경우 사용 가능하다.
• 위 특성에 따라 Convex Hull Trick이나 Monotone Queue Optimization에도 적용 가능하다.
  • DP식만 구했다면 뇌를 비우고 리차오를 짜면 된다는 것이 큰 장점.
  • 하지만 DP opt는 어디까지나 리차오의 활용법 중 하나에 불과하다는 것을 주의하자.
    • 예시로, 반평면 땅따먹기 2는 DP opt와 관계가 없지만 리차오로 풀 수 있다.
  • O(NlgN) CHT와 비교했을 때 3~4배정도 느리다.
  • O(N) CHT와 비교했을 때 10배정도 느리다.

구현

• f(j, i)는 사용자가 직접 코드를 짜야 한다. 위 예시에서는 나무 자르기의 DP식을 써넣었다.
• cmp에서 부등호가 <면 최소, >면 최대를 구한다.
• qry(x) = x에서 최소/최대인 함수의 인덱스를 구한다.
  • 실제 값을 알고 싶다면 f(qry(x), x)처럼 쓴다.
• add(a) = 인덱스가 a인 함수을 트리에 추가한다.
• 배열의 값은 0부터 시작한다.
  • 1부터 시작하도록 바꿀 수는 있으나, 권장하지 않는다.

참고

• f(j, i)는 f(i, x)라고 생각해도 된다.
• a ?: b는 GCC 및 Clang의 비표준 문법으로, a ? a : b와 같은 의미이다.