题目： E-card oj1811

思路：线段树内存直线的k和b，线段树存x，当某个区间的左右端点代入关系始终严格优于或劣于带修改的值，则修改区间。否则继续分散到两个子区间重复操作。

代码：

#include
      
       #define LL long long#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=100005;struct node{
    int l,r,a,b;}q[N];struct Tree{LL k,b;}t[N*12];int n,m,b[N*3],cnt;LL maxn[N*12];int read(){
    int x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=x*10+ch-48;return f*x;}void update(int x,int l,int r,int ql,int qr,LL k,LL bi){    int mid=(l+r)>>1;    if(ql<=l&&r<=qr){        LL q1,q2,w1,w2;w1=(LL)b[l]*k+bi;w2=(LL)b[r]*k+bi;      q1=(LL)b[l]*t[x].k+t[x].b;q2=(LL)b[r]*t[x].k+t[x].b;        if(w1<=q1&&w2<=q2)return;      if(w1>q1&&w2>q2){t[x].k=k;t[x].b=bi;return;}if(l==r)return;      update(x<<1,l,mid,ql,qr,k,bi);update(x<<1|1,mid+1,r,ql,qr,k,bi);return;    }    if(ql<=mid)update(x<<1,l,mid,ql,qr,k,bi);    if(mid
       
        <<1|1,mid+1,r,ql,qr,k,bi);}LL query(int x,int l,int r,int pos){    LL res;res=(LL)b[pos]*t[x].k+t[x].b;    if(l==r)return res;int mid=(l+r)>>1;    if(pos<=mid)res=max(res,query(x<<1,l,mid,pos));    else res=max(res,query(x<<1|1,mid+1,r,pos));    return res;}void change(int x,int l,int r,int pos,LL res){    if(l==r){maxn[x]=max(res,maxn[x]);return;}int mid=(l+r)>>1;    if(pos<=mid)change(x<<1,l,mid,pos,res);    else change(x<<1|1,mid+1,r,pos,res);    maxn[x]=max(maxn[x<<1],maxn[x<<1|1]);}int getans(int x,int l,int r){    if(l==r)return l;int mid=(l+r)>>1;    if(maxn[x<<1]>=maxn[x<<1|1])return getans(x<<1,l,mid);    else return getans(x<<1|1,mid+1,r);}int main(){    n=read();m=read();b[++cnt]=1;    for(int i=1;i<=m;i++){        int op;op=read();        if(op==1){q[i].l=read();q[i].r=read();q[i].a=read();q[i].b=read();b[++cnt]=q[i].l;b[++cnt]=q[i].r;}        else {q[i].l=read();q[i].r=0;b[++cnt]=q[i].l;}    }    sort(b+1,b+1+cnt);cnt=unique(b+1,b+1+cnt)-b-1;    for(int i=1;i<=m;i++){        if(q[i].r==0){            q[i].l=lower_bound(b+1,b+1+cnt,q[i].l)-b;            LL res;res=query(1,1,cnt,q[i].l);change(1,1,cnt,q[i].l,res);printf("%d\n",b[getans(1,1,cnt)]);        }        else{            q[i].l=lower_bound(b+1,b+1+cnt,q[i].l)-b;q[i].r=lower_bound(b+1,b+1+cnt,q[i].r)-b;            update(1,1,cnt,q[i].l,q[i].r,(LL)q[i].a,(LL)q[i].b-(LL)q[i].a*(LL)b[q[i].l]);        }    }  return 0;}
       
      

这个思路也可以运用到带条件的斜率优化，用线段树维护斜率优化（oj3629）