본문 바로가기

Algorithm/Data structure

Li Chao Tree

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

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

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

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

 

 

12795번: 반평면 땅따먹기

첫 줄에는 게임을 진행한 정보의 개수 Q(1 ≤ Q ≤ 200,000)이 주어지며, 이어서 Q 줄에 걸쳐 각 정보가 주어진다. 각 줄의 첫 번째 숫자가 1일 경우 이어서 2개의 정수 a, b(|a| ≤ 1,000,000, |b| ≤ 1,000,000,

www.acmicpc.net

 

#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번: 특공대

입력은 세 줄로 구성된다. 첫 번째 줄에 전체 병사들 수인 양의 정수 n이 주어진다. 두 번째 줄에 특공대의 조정된 전투력 계산 등식의 계수인 세 정수 a, b, c가 주어진다. 마지막 줄에 병사들 1, 2,

www.acmicpc.net

 

#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';
}

 

'Algorithm > Data structure' 카테고리의 다른 글

경로 가중치 합 hld 구현 코드  (0) 2021.07.06
Segment Tree and Lazy Propagation  (0) 2021.05.28
연속합 최대 Segment Tree  (2) 2021.05.22
Bottom-Up Segment Tree  (2) 2021.04.18
Fenwick Tree  (4) 2021.04.04