将高度公式拆开，得到 \(h=-\frac{1}{2}gx^2+(gl+v)x-\frac{1}{2}gl^2-vl+a(x\in\left[l,r\right])\)，因为给定 \(x\) 时 \(-\frac{1}{2}gx^2\) 是个定值，所以先忽略。可以发现后半部分是个线段的形式，求 \(h_{\max}\) 就是求线段在 \(x\) 处取得的最大值，用李超树维护，动态开点即可。需要注意的是，query 函数最好返回的是取得最大值的线段是哪一条，而不是返回最大值，减少精度误差。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define LD long double
using namespace std;
const LD g=9.8;
const int inf=1e9,N=1e5+10;
int n,cnt,root;
LD k[N],b[N];
LD get(LD x,int id){
return k[id]*x+b[id];
}
namespace Seg_Tree{
struct node{
int ch[2],mx;
}tr[N<<5];
#define ls(p) tr[p].ch[0]
#define rs(p) tr[p].ch[1]
#define V(x) x/1000.0L
void update(int &p,int l,int r,int u){
if(!p){
p=++cnt;
}
int mid=(l+r)>>1,&v=tr[p].mx;
if(get(V(mid),v)<get(V(mid),u)){
swap(u,v);
}
if(get(V(l),v)<get(V(l),u)){
update(ls(p),l,mid,u);
}
if(get(V(r),v)<get(V(r),u)){
update(rs(p),mid+1,r,u);
}
}
void change(int &p,int l,int r,int q_l,int q_r,int u){
if(!p){
p=++cnt;
}
if(q_l<=l&&r<=q_r){
update(p,l,r,u);
return;
}
int mid=(l+r)>>1;
if(q_l<=mid){
change(ls(p),l,mid,q_l,q_r,u);
}
if(q_r>mid){
change(rs(p),mid+1,r,q_l,q_r,u);
}
}
int query(int p,int l,int r,int pos){
if(!p||l==r){
return tr[p].mx;
}
int mid=(l+r)>>1,ans=0;
if(pos<=mid){
ans=query(ls(p),l,mid,pos);
}
else{
ans=query(rs(p),mid+1,r,pos);
}
if(get(V(pos),tr[p].mx)<get(V(pos),ans)){
return ans;
}
return tr[p].mx;
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
scanf("%d",&n);
char s[100];
b[0]=-1e18;
for(int i=1;i<=n;i++){
scanf("%s",s);
if(s[0]=='a'){
LD x,v,l,r;
scanf("%Lf%Lf%Lf%Lf",&x,&v,&l,&r);
k[i]=g*l+v;
b[i]=-g*l*l/2.0L-v*l+x;
Seg_Tree::change(root,-inf,inf,l*1000,r*1000,i);
}
else{
LD x;
scanf("%Lf",&x);
int ans=Seg_Tree::query(root,-inf,inf,x*1000);
if(!ans){
puts("Undefined");
continue;
}
printf("%Lf\n",-g*x*x/2.0L+get(x,ans));
}
}
return 0;
}