其中第一种转移显然是个前缀 $\max$, 因为已经按 $r_i$ 排过序了所以直接二分找到最后一个做这种贡献的位置然后取前缀 $\max$ 就可以了.
第二种转移需要拆一拆...
$$
\begin{aligned}
dp_i&=\max_{j
其中 $\max$ 里面是一个一次函数的形式, 可以用李超树来搞.
等一下!
李超树怎么处理 $r_j\ge l_i$ 这个限制呢? 换句话说, 我们怎么在计算第二部分贡献的时候排除 $r_j
const int MAXN=1e5+10;
typedef long long intEx;
struct Point{
int l;
int r;
intEx w;
};
Point P[MAXN];
int n;
int s[MAXN];
intEx smax[MAXN];
struct Line{
intEx k;
intEx b;
Line(const intEx& a,const intEx& b):k(a),b(b){}
inline intEx operator()(const int& x)const{
return k*s[x]+b;
}
};
struct Node{
int l;
int r;
Line f;
Node* lch;
Node* rch;
~Node();
Node(int,int);
intEx Query(int);
void Insert(Line);
};
int main(){
freopen("radar.in","r",stdin);
freopen("radar.out","w",stdout);
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
P[i].l=x-y;
P[i].r=x+y;
s[i]=P[i].l;
P[i].w=4ll*y*y-4ll*c*y;
}
std::sort(P+1,P+n+1,
[](const Point& a,const Point& b){
return a.rQuery(h)-1ll*P[i].l*P[i].l+P[i].w;
int p=std::lower_bound(P+1,P+n+1,P[i].l,
[](const Point& a,const int& b){
return a.rInsert(Line(2*P[i].r,dp-1ll*P[i].r*P[i].r));
smax[i]=std::max(smax[i-1],dp);
}
printf("%lld.%02lld\n",smax[n]>>2,(smax[n]&3)*25);
delete N;
}
return 0;
}
intEx Node::Query(int x){
if(this->l==this->r)
return this->f(x);
else{
if(x<=this->lch->r)
return std::max(this->lch->Query(x),this->f(x));
else
return std::max(this->rch->Query(x),this->f(x));
}
}
void Node::Insert(Line f){
int mid=(this->l+this->r)>>1;
if(f(mid)>this->f(mid))
std::swap(f,this->f);
intEx ld=this->f(this->l)-f(this->l);
intEx rd=this->f(this->r)-f(this->r);
if(ld>=0&&rd>=0)
return;
else if(rd>=0)
this->lch->Insert(f);
else
this->rch->Insert(f);
}
Node::~Node(){
if(this->lch)
delete this->lch;
if(this->rch)
delete this->rch;
}
Node::Node(int l,int r):l(l),r(r),f(0,-1e18),lch(NULL),rch(NULL){
if(l!=r){
int mid=(l+r)>>1;
this->lch=new Node(l,mid);
this->rch=new Node(mid+1,r);
}
}
```
![](https://pic.rvalue.moe/2021/08/02/254b4cc06255f.png)