yukicoder : No.2404 Vertical Throw Up

これはすんなり。
https://yukicoder.me/problems/no/2404

問題

この星では重力加速度はAとする。
高さ0の場所から、ある時点で真上に石を投げると、時刻tでの高さはf(t) = max(0, -at^2+bt+c)のように表現できる。

以下のクエリに答えよ。

• 投げる石を追加する。投げる時刻と、その石が地面に落ちる時刻が与えられるので、それを満たすように石を投げる。
• 時刻が指定されるので、石のうち高さの最大値を求める。

解法

時刻pに投げた石が時刻qに落ちる場合、その石の高さはf(t) = max(0, -a(t-p)(t-q))となり、b=-a*(p+q)、c=-a*p*qと定まる。
このクエリに答えるには、tの一次式が沢山あるときの最大値を求めればいいので、Le Chao Treeで解ける。

template<typename V> struct LeChaoTree {
	static const V inf=3LL<<60;
	const ll range=1<<30;
	const bool cmptype=1; //true:max false:min
	struct node {
		node(V a=0,V b=-inf) : A(a),B(b){ le=ri=NULL;}
		V val(ll x) { return A*x+B;}
		V A,B;  // Ax+B
		node *le, *ri;
	};
	
	node* root;
	LeChaoTree() { root=new node(0,-inf);}
	
	void add(node* n, V a,V b,ll L,ll R) {
		ll M=(L+R)/2;
		
		bool lef=(n->val(L) > a*L+b);
		bool mid=(n->val(M) > a*M+b);
		bool ri=(n->val(R) > a*R+b);
		
		if(lef&&ri) return;
		if(!lef&&(!ri || R-L==1)) {
			n->A=a;
			n->B=b;
			return;
		}
		
		if(R-L==1) return;
		if(!n->ri) n->ri=new node();
		if(!n->le) n->le=new node();
		add(n->ri,a,b,M,R);
		add(n->le,a,b,L,M);
	}
	
	void add(V a,V b) { 
		if(!cmptype) a=-a,b=-b;
		add(root,a,b,0,range);
	}
	
	V query(ll x) {
		V ret=-inf;
		node* cur=root;
		ll L=0, R=range;
		while(cur) {
			ret=max(ret,cur->val(x));
			ll m=(L+R)/2;
			if(x<m) cur=cur->le, R=m;
			else cur=cur->ri, L=m;
			
		}
		
		if(!cmptype) ret=-ret;
		return ret;
	}
};
LeChaoTree<ll> lct;
ll A;
ll Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>Q;
	while(Q--) {
		ll P,Q;
		cin>>i;
		if(i==1) {
			cin>>P>>Q;
			lct.add((P+Q),-P*Q);
		}
		else {
			cin>>P;
			Q=A*max(0LL,lct.query(P)-P*P);
			cout<<Q<<endl;
		}
	}
}

まとめ

LCTのライブラリがあれば簡単。