P4254 [JSOI2008]Blue Mary开公司

李超线段树模板题

李超线段树 维护一个坐标系 x轴从1-n的区间，显然你x坐标的最大值不要超过1e5 （特殊问题可以正无穷，具体问题具体分析）

从[1,N]开始每次从mid划分区间

然后根据mid去更新区间的最优线段

详见洛谷日报266

https://www.luogu.com.cn/blog/fzber0103/Li-Chao-Tree

注意一下  李超线段树的查询

从大区间依次往小区间去查，一直更新答案，

#include<cstdio>
#include<iostream>
#include<algorithm>
const int N=500005;
int tot=0;
char s[15];
int tag[4000005];//记录当前区间的最优线段
double k[100005],b[100005];//斜率和截距
inline double calc(int i,int x) {return k[i]*(x-1)+b[i];}//因为第一天他直接取截距，第二天才会根据斜率上升一下，所以x-1
void change(int p,int l,int r,int x) {
    if(l==r) {
        if(calc(tag[p],l)<calc(x,l)) tag[p]=x;
        return;
    }
    if(!tag[p]) {tag[p]=x;return;}
    else {
        int mid=l+r>>1;
        double y1=calc(tag[p],mid),y2=calc(x,mid);
        if(k[tag[p]]<k[x]) {  //情况1
            if(y1<=y2) {change(p*2,l,mid,tag[p]);tag[p]=x;} 
            else {change(p*2+1,mid+1,r,x);}
        }
        else if(k[tag[p]]>k[x]) { //情况2 
            if(y1<=y2) {change(p*2+1,mid+1,r,tag[p]);tag[p]=x;}
            else {change(p*2,l,mid,x);}
        }
        else if(b[tag[p]]<b[x]) {tag[p]=x;}  //情况3 直接完全凌驾于旧直线，直接取代
    } 
}
double query(int p,int l,int r,int x) {
    if(l==r) return calc(tag[p],l);
    double res=calc(tag[p],x);
    int mid=l+r>>1;
    if(x<=mid) res=std::max(res,query(p*2,l,mid,x));
    else res=std::max(res,query(p*2+1,mid+1,r,x));
    return res;
}
int main() {
    int n;
    std::cin>>n;
    for(register int i=1;i<=n;++i) {
        std::cin>>s;
        if(s[0]=='Q') {
            int t;
            std::cin>>t;
            if(tot==0) printf("0
");
            else printf("%d
",(int)query(1,1,N,t)/100);
        }
        else {
            double s,p;++tot;
            std::cin>>b[tot]>>k[tot];
            change(1,1,N,tot);
        }
    }
    return 0;
}