BOJ 20608 Dynamic Convex Hull

문제 링크입니다.

문제 요약

$f(x) = (x-a)^4 + b$ 꼴의 함수들의 집합에 원소를 추가/삭제하면서 쿼리로 $x$가 주어질 때마다 함숫값 $f(x)$의 최솟값을 구하세요.

풀이

$(x-a)^4 + b$ 꼴의 서로 다른 두 함수의 교점은 1개 이하임을 관찰할 수 있습니다.

따라서 최솟값/최댓값을 구함에 있어 직선을 다루는 것과 큰 차이가 없습니다. 리-차오 트리를 이용해 함수들을 관리해 줄 수 있겠네요.

원소를 삭제하기 위해 쿼리를 오프라인으로 처리합니다. 각 함수들이 집합에 존재하는 시간을 쿼리 번호를 기준으로 저장해 둔 뒤, 세그먼트 트리 내려가듯이 시간 구간에 대한 분할 정복을 수행합니다. 이때 함수가 이번 구간 전체에서 살아있다면 함수를 리-차오 트리에 추가한 뒤, 구간 안에서의 쿼리를 처리하고 함수를 삭제합니다. 이런 방식을 취하는 이유는 최댓값/최솟값 업데이트에 역원을 먹여서 되돌리는 게 불가능해, 이전 상태를 기록해 뒀다 되돌리는 방식으로 처리해야 하기 때문입니다.

퍼시스턴트 세그먼트 트리의 구조를 빌려 와서 롤백 기능을 만들어 주면 총 시간 복잡도 ${\cal O}(N \lg ^2 N)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll INF = LONG_LONG_MAX;

struct LiChao{
	struct Func{
		ll a, b;
		Func(ll a, ll b) : a(a), b(b) {}
	};
	struct Node{
		Node *l, *r; int idx;
		Node(int idx = -1) : idx(idx) {l = r = nullptr;}
	};
	vector<Func> F; vector<Node*> root;
	LiChao(){}
	ll f(int idx, ll x){
		if(F[idx].b == INF) return INF;
		ll t = (x-F[idx].a);
		return t*t*t*t+F[idx].b;
	}
	void init(Node* now, int l, int r){
		if(l == r) return;
		now->l = new Node(0); init(now->l, l, mid);
		now->r = new Node(0); init(now->r, mid+1, r);
	}
	void init(){
		F.clear(); root.clear(); F.push_back(Func(0, INF)); Node* tmp = new Node(0); root.push_back(tmp);
		init(root[0], 1, 50000);
	}
	void upd(Node* pre, Node* now, int l, int r, int low){
		int high = pre->idx;
		if(f(low, l) > f(high, l)) swap(low, high);
		if(f(low, r) <= f(high, r)){now->l = pre->l; now->r = pre->r; now->idx = low; return;}
		if(f(low, mid) <= f(high, mid)){now->idx = low; now->l = pre->l; now->r = new Node(0); upd(pre->r, now->r, mid+1, r, high);}
		else{now->idx = high; now->r = pre->r; now->l = new Node(0); upd(pre->l, now->l, l, mid, low);}
	}
	ll qry(Node* now, int l, int r, int x){
		ll ret = f(now->idx, x);
		if(l == r) return ret;
		if(x <= mid) return min(ret, qry(now->l, l, mid, x));
		else return min(ret, qry(now->r, mid+1, r, x));
	}
	ll qry(int x){
		ll ret = qry(root.back(), 1, 50000, x);
		if(ret == INF) ret = -1;
		return ret;
	}
	void add_func(int idx){Node* tmp = new Node(0); root.push_back(tmp); upd(root[root.size()-2], root.back(), 1, 50000, idx);}
	void del_func(){root.pop_back();}
};

map<int, int> mp;
vector<int> tree[404040];
int Q[101010]; ll A[101010];
LiChao lct;

void init_tree(int now, int l, int r){
	tree[now].clear(); if(l == r) return;
	init_tree(now<<1, l, mid); init_tree(now<<1|1, mid+1, r);
}

void upd_tree(int now, int l, int r, int L, int R, int v){
	if(l > R || L > r) return;
	if(L <= l && r <= R){tree[now].push_back(v); return;}
	upd_tree(now<<1, l, mid, L, R, v); upd_tree(now<<1|1, mid+1, r, L, R, v);
}

void go(int now, int l, int r){
	for(auto& i : tree[now]) lct.add_func(i);
	if(l == r){if(Q[l] > 0) A[l] = lct.qry(Q[l]);}
	else go(now<<1, l, mid), go(now<<1|1, mid+1, r);
	for(auto& i : tree[now]) lct.del_func();
}

void solve(){
	int n, q; cin >> n >> q;
	mp.clear(); lct.init(); init_tree(1, 1, q); memset(Q, 0, sizeof(Q));
	for(int i = 1; i <= n; i++){
		ll a, b; cin >> a >> b; lct.F.push_back(LiChao::Func(a, b)); mp[i] = 1;
	}
	for(int i = 1; i <= q; i++){
		int op; cin >> op;
		if(op == 1){
			ll a, b; cin >> a >> b; lct.F.push_back(LiChao::Func(a, b)); n++; mp[n] = i;
		}
		if(op == 2){
			int t; cin >> t; upd_tree(1, 1, q, mp[t], i, t); mp[t] = 0;
		}
		if(op == 3) cin >> Q[i];
	}
	for(auto& [key, val] : mp) if(val) upd_tree(1, 1, q, val, q, key);
	go(1, 1, q); for(int i = 1; i <= q; i++) if(Q[i] > 0) cout << A[i] << '\n';
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int T; cin >> T; while(T--) solve();
}