Li Chao Tree

리차오 트리 특: CHT를 사용할 때 필요한 기울기의 단조성이 없어도 된다.

트리 안에 식(흔히 일차함수)을 넣는 것과 점 최소/최대 쿼리를 O(logN)에 해주는 자료구조.

외우기 쉽고 범용성도 좋아 유용할 것 같다는 생각이 든다.

CHT로 풀리는 문제는 시간이 빡빡하지 않은 이상 리차오 트리로도 풀린다.

 

12795번: 반평면 땅따먹기

 

#include<bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
const ll INF=1e18;
struct LiChao {
	struct line {
		ll a,b;
		ll f(ll x) { return a*x+b; }
	};
	line base={0,-INF};
	struct node {
		int l,r; ll xl,xr;
		line ln;
	};
	vector<node> tree;
	void init(ll xmin,ll xmax) {
		tree.push_back({-1,-1,xmin,xmax,base});
	}
	void update(int n,line nl) {
		ll xl=tree[n].xl, xr=tree[n].xr;
		ll xm=xl+xr>>1;
		line low=tree[n].ln, high=nl;
		if(low.f(xl)>=high.f(xl)) swap(low,high);
		if(low.f(xr)<=high.f(xr)){ tree[n].ln=high; return; }
		if(low.f(xm)<=high.f(xm)){
			tree[n].ln=high;
			if(tree[n].r==-1){
				tree[n].r=tree.size();
				tree.push_back({-1,-1,xm+1,xr,base});
			}
			update(tree[n].r,low);
		}
		else{
			tree[n].ln=low;
			if(tree[n].l==-1){
				tree[n].l=tree.size();
				tree.push_back({-1,-1,xl,xm,base});
			}
			update(tree[n].l,high);
		}
	}
	ll query(int n,ll x) {
		if(n==-1) return -INF;
		ll xm=tree[n].xl+tree[n].xr>>1;
		if(x<=xm) return max(tree[n].ln.f(x),query(tree[n].l,x));
		else return max(tree[n].ln.f(x),query(tree[n].r,x));
	}
} tree;
int main()
{
	fastio;
	tree.init(-1e12,1e12);
	int q; cin >> q;
	while(q--){
		ll t,a,b; cin >> t;
		if(t==1){
			cin >> a >> b;
			tree.update(0,{a,b});
		}
		else{
			cin >> a;
			cout << tree.query(0,a) << '\n';
		}
	}
}

 

 

2021.07.04 update:

구조체 없는 버전. 시간, 메모리 비슷, 직관적.

 

4008번: 특공대

 

#include <bits/stdc++.h>
using namespace std;
#define xm (xl + xr >> 1)
typedef long long ll;
const ll INF = 1e18;

struct Line {
	ll a, b;
	ll f(ll x) { return a * x + b; }
	Line() : a(0), b(-INF) {}
	Line(ll a, ll b) : a(a), b(b) {}
};

struct Node {
	ll xl, xr; int l = -1, r = -1;
	Line ln = Line();
};

vector<Node> tree;

void init(ll xmin, ll xmax) {
	tree.push_back({xmin, xmax});
}
void update(Line L, int i = 0) {
	ll xl = tree[i].xl, xr = tree[i].xr;
	Line low = tree[i].ln, high = L;
	if(low.f(xl) > high.f(xl)) swap(low, high);
	if(low.f(xr) <= high.f(xr)) return tree[i].ln = high, void();
	if(low.f(xm) <= high.f(xm)) {
		tree[i].ln = high;
		if(tree[i].r == -1) {
			tree[i].r = tree.size();
			tree.push_back({xm + 1, xr});
		}
		update(low, tree[i].r);
	}
	else {
		tree[i].ln = low;
		if(tree[i].l == -1) {
			tree[i].l = tree.size();
			tree.push_back({xl, xm});
		}
		update(high, tree[i].l);
	}
}
ll query(ll x, int i = 0) {
	if(i == -1) return -INF;
	ll xl = tree[i].xl, xr = tree[i].xr;
	if(x <= xm) return max(tree[i].ln.f(x), query(x, tree[i].l));
	else return max(tree[i].ln.f(x), query(x, tree[i].r));
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n; cin >> n;
	ll a, b, c; cin >> a >> b >> c;
	init(0, 1e8);
	ll sum = 0, dp = 0;
	for(int i = 1; i <= n; i++) {
		update({-2 * a * sum + b, dp - b * sum + a * sum * sum});
		ll x; cin >> x; sum += x;
		dp = query(sum) + a * sum * sum + c;
	}
	cout << dp << '\n';
}