%%%李超。
李超线段树是解决最优势线段问题（线段线段树），支持插入一条线段，查询单点最优势点。
线段树上的每一个端点存的都是这个区间内的最优势线段。
算法流程：
插入
假设我们用线段树查到区间是这个被这个线段覆盖的，现在我们要判断它是否具有优势。
1.将左右两个端点进行比较，若这个线段都是优势的，直接替换；
若都不优势，这条线段就没用了，直接删掉。
2.如果上述两个条件都不符合，就进入这一步。
此时这个线段具有部分优势。
比较中点，将优势线段存入节点，将不优势线段插入这条线段的优势部分递归操作。
Bzoj1568
裸的，注意全开double！！！
#include<iostream> #include<cstdio> #define N 50009 using namespace std; double ib[N<<2],ik[N<<2],x,y; int n; char s[10]; double calc(double b,double k,double l){ return b+k*(l-1); } void add(int cnt,int l,int r,double b,double k){ int mid=(l+r)>>1; if(!ib[cnt]){ ib[cnt]=b; ik[cnt]=k; } else{ bool ll=calc(ib[cnt],ik[cnt],l)<=calc(b,k,l); bool rr=calc(ib[cnt],ik[cnt],r)<=calc(b,k,r); if(ll&&rr){ ib[cnt]=b; ik[cnt]=k; return; } if(!ll&&!rr)return; if(calc(ib[cnt],ik[cnt],mid)<calc(b,k,mid)){ double xx=ib[cnt],yy=ik[cnt]; ib[cnt]=b;ik[cnt]=k; if(ll)add(cnt<<1|1,mid+1,r,xx,yy); else add(cnt<<1,l,mid,xx,yy); } else{ if(ll)add(cnt<<1,l,mid,b,k); else add(cnt<<1|1,mid+1,r,b,k); } } } void query(int x){ int cnt=1,l=1,r=50000; double ans=0; while(l<r){ int mid=(l+r)>>1; if(ib[cnt])ans=max(ans,calc(ib[cnt],ik[cnt],x)); if(mid>=x)r=mid,cnt<<=1; else l=mid+1,cnt=cnt<<1|1; } ans=max(ans,calc(ib[cnt],ik[cnt],x)); printf("%d ",(int)ans/(int)100); } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%s",s); if(s[0]=='Q'){ scanf("%lf",&x); query(x); } else{ scanf("%lf%lf",&x,&y); add(1,1,50000,x,y); } } return 0; }
Segment
和上一个相比，插入带区间。
#include<iostream> #include<cstdio> #define N 40009 #define NN 100009 using namespace std; int id[N<<2]; double kk[NN],bb[NN]; int x0,y0,y1,x1,k; const int nine=1e9; double calc(int id,int x) { return bb[id]+(double)kk[id]*x; } void add(int cnt,int l,int r,int L,int R,int tot) { if(l>r)return; if(l>=L&&r<=R) { if(!id[cnt]) { id[cnt]=tot; return; } bool le=calc(id[cnt],l)<=calc(tot,l); bool ri=calc(id[cnt],r)<=calc(tot,r); if(le&&ri) { id[cnt]=tot; return; } if(!le&&!ri)return; int mid=(l+r)>>1; double pu=calc(tot,mid); if(calc(id[cnt],mid)<pu) { if(le)add(cnt<<1|1,mid+1,r,L,R,id[cnt]); else add(cnt<<1,l,mid,L,R,id[cnt]); id[cnt]=tot; } else { if(le)add(cnt<<1,l,mid,L,R,tot); else add(cnt<<1|1,mid+1,r,L,R,tot); } } int mid=(l+r)>>1; if(mid>=L)add(cnt<<1,l,mid,L,R,tot); if(mid<R)add(cnt<<1|1,mid+1,r,L,R,tot); } inline int qq(int k) { int l=1,r=39989,mid,as=0,cnt=1; double pu=0; while(l<r) { int mid=(l+r)>>1; if(id[cnt]) { if(calc(id[cnt],k)>pu) { pu=calc(id[cnt],k); as=id[cnt]; } } if(k<=mid) { r=mid;; cnt<<=1; } else { l=mid+1; cnt=cnt<<1|1; } } if(id[cnt]) if(calc(id[cnt],k)>pu) as=id[cnt]; return as; } int main() { int n,tag,ans=0,tot=0; scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%d",&tag); if(tag) { scanf("%d%d%d%d",&x0,&y0,&x1,&y1); x0=(x0+ans-1)%39989+1;y0=(y0+ans-1)%nine+1; x1=(x1+ans-1)%39989+1;y1=(y1+ans-1)%nine+1; if(x0>x1)swap(x0,x1),swap(y0,y1); if(x0==x1)kk[++tot]=0,bb[tot]=max(y0,y1); else kk[++tot]=(double)(y0-y1)/(x0-x1),bb[tot]=y0-kk[tot]*x0; add(1,1,39989,x0,x1,tot); } else { scanf("%d",&k);k=(k+ans-1)%39989+1; printf("%d ",ans=qq(k)); } } return 0; }