题目链接：戳我
这相当于是一个李超线段树的模板qwqwq，题解就不多说了。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 500010
using namespace std;
int n,m;
int t[MAXN<<2];
char s[10];
double k[MAXN<<1],b[MAXN<<1];
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline double calc(int x,int cnt){return k[x]*(cnt-1)+b[x];}
inline void update(int x,int l,int r,int now)
{
if(l==r)
{
if(calc(x,l)<calc(now,l)) t[x]=now;
return;
}
int mid=(l+r)>>1;
if(k[t[x]]>k[now])
{
if(calc(now,mid)>calc(t[x],mid)) update(rs(x),mid+1,r,t[x]),t[x]=now;
else update(ls(x),l,mid,now);
}
if(k[t[x]]<k[now])
{
if(calc(now,mid)>calc(t[x],mid)) update(ls(x),l,mid,t[x]),t[x]=now;
else update(rs(x),mid+1,r,now);
}
}
inline double query(int x,int l,int r,int k)
{
if(l==r) return calc(t[x],k);
int mid=(l+r)>>1;
if(k<=mid) return max(calc(t[x],k),query(ls(x),l,mid,k));
else return max(calc(t[x],k),query(rs(x),mid+1,r,k));
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
freopen("ce.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s);
if(s[0]=='P')
{
++m;
scanf("%lf%lf",&b[m],&k[m]);
update(1,1,MAXN,m);
}
else
{
int cur;
scanf("%d",&cur);
//printf("%.5lf
",max(0.0,query(1,1,n,cur)));
printf("%d
",(int)max(0.0,query(1,1,MAXN,cur)/100));
}
}
return 0;
}
不过落谷题目上面标的数据范围貌似是有点问题的。。。
李超线段树简单学习笔记
用途：
支持插入n条线段，然后维护区间最优势线段。（什么是区间最优势线段？比如说求最大值，是这个区间里面最大值“显露”的最多的）
来一张图片吧——
过程：（我使用斜率在维护的，不是左右端点qwqwq）
就是分两种情况：（我们设当前区间的最优势线段为x,新加入线段为now，y(a,mid)表示在x==mid的时候的y值）
- k(x)>k(now)
- y(now,mid)>y(x,mid)这时候左子区间now是优势线段，直接更改当前区间最优势线段即可。然后递归处理右子区间（注意这里要更换now为x）。
- else 这个时候直接递归处理左子区间即可。
- k(x)<k(now) 道理同上
- 斜率相等的时候不需要任何操作，直接在叶子节点更改即可（但是感觉这样子会比判断左右端点的写法慢。。。）
解释一下一个比较容易疑惑的点（其实我也不知道自己能不能解释清楚，如果有不理解的地方还请多画画图）
就是为什么递归处理子区间的时候，更换now为x不会丢失线段信息？？？
因为我们首先可以确定一点，每一次分的区间（闭区间），都至少有一个区间里面包含了至少一个交点。
所以在节点的同一侧，一定是最优势线段已经记录好了，所以一定不会出现丢失信息的情况。（因为查询的时候有一路向上取最值确保啦！）
时间复杂度：
- 插入(O(logn))
- 查询(O(logn))