tests/li_chao_tree.test.cpp

View this file on GitHub
Last update: 2024-02-01 17:09:56-05:00
Problem: https://judge.yosupo.jp/problem/line_add_get_min

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min"
#include "../content/data_structures/li_chao_tree.h"

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin.exceptions(cin.failbit);
	
	int n, q;
	cin>>n>>q;
	
	sparse_li_chao_tree<ll> st;
	st.init(-1e9, 1e9, LLONG_MAX, [](auto x, auto y){ return min(x, y); });
	while(n--){
		ll a, b;
		cin>>a>>b;
		st.add({a, b});
	}
	while(q--){
		int op;
		cin>>op;
		if(op == 0){
			ll a, b;
			cin>>a>>b;
			st.add({a, b});
		}
		else{
			ll x;
			cin>>x;
			cout<<st.get(x)<<'\n';
		}
	}
}

#line 1 "tests/li_chao_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min"
#line 1 "content/utils/template.h"
/**
 * @brief My starter code
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define makeunique(x) (x).erase(unique((x).begin(), (x).end()), (x).end());

#ifdef LOCAL
template<typename T> void pr(T a){std::cerr<<a<<std::endl;}
template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args> void pr(Args... args){}
#endif

using namespace std;
using ll = long long;
using pii = pair<int, int>;
#line 3 "content/data_structures/li_chao_tree.h"

/**
 * @brief Li Chao Tree
 * @docs docs/li_chao_tree.md
 */

template<typename T> struct line{
	T m, b;
	T eval(T x){ return m*x + b;}
};

template<typename T> struct sparse_li_chao_tree{
	int LS, RS;
	T def;
	function<T(T, T)> merge;
	
	struct node{
		node *lc, *rc;
		line<T> val;
		node(line<T> _val){
			lc = rc = nullptr;
			val = _val;
		}
	};
	node *rt = nullptr;
	
	// merge() should be min or max
	void init(int _LS, int _RS, T _def, function<T(T, T)> _merge){
		LS = _LS;
		RS = _RS;
		def = _def;
		merge = _merge;
	}

	#define nm (nl+(nr-nl)/2)
	// this works for negative indices too, unlike (nl+nr)/2
	
	void _add(line<T> ln, int nl, int nr, node *&cur){
		assert(nl <= nr);
		if(!cur){
			cur = new node(ln);
			return;
		}
		bool bl = ln.eval(nl) < cur->val.eval(nl);
		bool bm = ln.eval(nm) < cur->val.eval(nm);
		if(bm) swap(cur->val, ln);
		if(nl == nr) return;
		bl != bm ? _add(ln, nl, nm, cur->lc) : _add(ln, nm+1, nr, cur->rc);
	}
	void add(line<T> ln){ _add(ln, LS, RS, rt); }
	
	T _get(T x, int nl, int nr, node *cur){
		if(!cur) return def;
		if(nl == nr) return cur->val.eval(x);
		if(x <= nm) return merge(cur->val.eval(x), _get(x, nl, nm, cur->lc));
		return merge(cur->val.eval(x), _get(x, nm+1, nr, cur->rc));
	}
	T get(T x){ return _get(x, LS, RS, rt); }

	#undef nm
};
#line 3 "tests/li_chao_tree.test.cpp"

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin.exceptions(cin.failbit);
	
	int n, q;
	cin>>n>>q;
	
	sparse_li_chao_tree<ll> st;
	st.init(-1e9, 1e9, LLONG_MAX, [](auto x, auto y){ return min(x, y); });
	while(n--){
		ll a, b;
		cin>>a>>b;
		st.add({a, b});
	}
	while(q--){
		int op;
		cin>>op;
		if(op == 0){
			ll a, b;
			cin>>a>>b;
			st.add({a, b});
		}
		else{
			ll x;
			cin>>x;
			cout<<st.get(x)<<'\n';
		}
	}
}