BZOJ1568: [JSOI2008]Blue Mary开公司
李超树，俗称超哥线段树，是国家队队爷李超发明出来专门解决这一类问题：
现有2种操作：
1. 在平面上插入一条直线$y=kx+b$
2. 求在$[l,r]$范围内直线上的点的纵坐标的最大值
对付这种问题，超哥线段树是这么解决的：
假设在$[l,r]$内原有的一条直线为$f(x)_ 1=k_1x+b_1$
在这个区间内加入的直线为$f(x)_ 2=k_2x+b_2$
而递归求解最多涉及到$log_2n$个节点。
所以这样的复杂度上限是$O(log_2^2n)$。
然后，这题还需要用到标记永久化。
即我们不下传标记，在求区间最大值的时候，每次访问到一个和询问区间有交集的区间，把答案和这个区间所维护的线段取$min$。
附代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#define LSON rt<<1
#define RSON rt<<1|1
#define DATA(x) a[x].data
#define MUL(x) a[x].k
#define ADD(x) a[x].v
#define SIGN(x) a[x].c
#define LSIDE(x) a[x].l
#define RSIDE(x) a[x].r
#define MAXN 100010
using namespace std;
int n,m;
struct Segment_Tree{
double data,k,v;
bool c;
int l,r;
}a[MAXN<<2];
inline int read(){
int date=0,w=1;char c=0;
while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
return date*w;
}
inline void pushup(int rt){
DATA(rt)=max(DATA(rt),max(DATA(LSON),DATA(RSON)));
}
void buildtree(int l,int r,int rt){
LSIDE(rt)=l;RSIDE(rt)=r;
DATA(rt)=0;SIGN(rt)=false;
if(l==r)return;
int mid=l+r>>1;
buildtree(l,mid,LSON);
buildtree(mid+1,r,RSON);
}
void change(double k,double v,int rt){
if(!SIGN(rt)){
SIGN(rt)=true;
MUL(rt)=k;ADD(rt)=v;
DATA(rt)=max(DATA(rt),max(k*LSIDE(rt),k*RSIDE(rt))+v);
return;
}
double l1=MUL(rt)*LSIDE(rt)+ADD(rt),l2=k*LSIDE(rt)+v;
double r1=MUL(rt)*RSIDE(rt)+ADD(rt),r2=k*RSIDE(rt)+v;
if(l2<=l1&&r2<=r1)return;
else if(l2>l1&&r2>r1){
MUL(rt)=k;ADD(rt)=v;
DATA(rt)=max(DATA(rt),max(k*LSIDE(rt),k*RSIDE(rt))+v);
return;
}
int mid=LSIDE(rt)+RSIDE(rt)>>1;
double mid1=MUL(rt)*mid+ADD(rt),mid2=k*mid+v;
if(l2<=l1){
if(mid2<=mid1)change(k,v,RSON);
else{
change(MUL(rt),ADD(rt),LSON);
MUL(rt)=k;ADD(rt)=v;
DATA(rt)=max(DATA(rt),max(k*LSIDE(rt),k*RSIDE(rt))+v);
}
}
else{
if(mid2<=mid1)change(k,v,LSON);
else{
change(MUL(rt),ADD(rt),RSON);
MUL(rt)=k;ADD(rt)=v;
DATA(rt)=max(DATA(rt),max(k*LSIDE(rt),k*RSIDE(rt))+v);
}
}
pushup(rt);
}
void update(int l,int r,double k,double v,int rt){
if(l<=LSIDE(rt)&&RSIDE(rt)<=r){
change(k,v,rt);
return;
}
int mid=LSIDE(rt)+RSIDE(rt)>>1;
if(l<=mid)update(l,r,k,v,LSON);
if(mid<r)update(l,r,k,v,RSON);
pushup(rt);
}
double query(int l,int r,int rt){
double ans=0;
if(l<=LSIDE(rt)&&RSIDE(rt)<=r)return DATA(rt);
int mid=LSIDE(rt)+RSIDE(rt)>>1;
if(l<=mid)ans=max(ans,query(l,r,LSON));
if(mid<r)ans=max(ans,query(l,r,RSON));
if(SIGN(rt))ans=max(ans,max(MUL(rt)*max(l,LSIDE(rt)),MUL(rt)*min(r,RSIDE(rt)))+ADD(rt));
return ans;
}
void work(){
char ch[15];
while(m--){
scanf("%s",ch);
if(ch[0]==‘P‘){
double x,y;
scanf("%lf%lf",&x,&y);
update(1,n,y,x-y,1);
}
else{
int x=read();
printf("%d\n",(int)query(x,x,1)/100);
}
}
}
void init(){
m=read();n=MAXN-10;
buildtree(1,n,1);
}
int main(){
init();
work();
return 0;
}
BZOJ1568: [JSOI2008]Blue Mary开公司
原文：https://www.cnblogs.com/Yangrui-Blog/p/9533241.html