比赛 contest by dark_moon 评测结果 EEEEEEEEEE
题目名称 ktt 最终得分 0
用户昵称 郑霁桓 运行时间 3.942 s
代码语言 C++ 内存使用 19.47 MiB
提交时间 2024-05-28 21:32:53
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[100005],b[100005],p,x,y,z;
struct N{
    long long aa,bb,lz,intr;
}t[400005];
long long build(long long p,long long l,long long r){
    t[p].lz=0;
    t[p].intr=100000000;
    if(l==r){
        t[p].aa=a[l];
        t[p].bb=b[l];
        return t[p].bb;
    }
    long long p1,p2;
    p1=build(p<<1,l,l+r>>1);
    p2=build(p<<1|1,(l+r>>1)+1,r);
    t[p].bb=max(p1,p2);
    if(p1<p2){
        t[p].aa=t[p<<1|1].aa;
    }else{
        t[p].aa=t[p<<1].aa;
    }
    return t[p].bb;
}
long long inter(N x,N y){
    if(x.aa>=y.aa&&x.bb>y.bb||x.aa<=y.aa&&x.bb<=y.bb){
        return 100000000;
    }
    if(x.aa>y.aa){
        return x.aa+x.bb-y.aa-y.bb-1/(x.aa-y.aa);
    }else{
        return y.aa+y.bb-x.aa-x.bb-1/(y.aa-x.aa);
    }
}
bool c(long long x,long long y){
    return t[x].bb>t[y].bb;
}
void pushup(long long p){
    if(c(x<<1,x<<1|1)){
        t[p]=t[p<<1|1];
    }else{
        t[p]=t[p<<1];
    }
    t[p].intr=min({t[p<<1].intr,t[p<<1|1].intr,inter(t[p<<1],t[p<<1|1])});
} 
void pushdown(long long p){
    t[p<<1].lz+=t[p].lz;
    t[p<<1].bb+=t[p].lz*t[p<<1].aa;
    t[p<<1].intr-=t[p].lz;
    t[p<<1|1].lz+=t[p].lz;
    t[p<<1|1].bb+=t[p].lz*t[p<<1|1].aa;
    t[p<<1|1].intr-=t[p].lz;
    t[p].lz=0;
    return;
}
void rebuild(long long p){
    if(t[p].intr){
        return;
    }
    pushdown(p);
    rebuild(p<<1);
    rebuild(p<<1|1);
    pushup(p);
    return;
}
void add(long long p,long long l,long long r,long long st,long long ed,long long v){
    if(l<=st&&ed<=r){
        t[p].bb+=t[p].aa*v;
        t[p].intr-=v;
        t[p].lz+=v;
        rebuild(p);
        return;
    }
    pushdown(p);
    if(st+ed>>1>=l){
        add(p<<1,l,r,st,st+ed>>1,v);
    }
    if(st+ed>>1+1<=r){
        add(p<<1+1,l,r,st+ed>>1+1,ed,v);
    }
    pushup(p);
    return;
}
long long sum(long long p,long long l,long long r,long long st,long long ed){
    if(l<=st&&ed<=r){
        return t[p].bb;
        pushdown(p);
    }
    long long s=0;
    if(st+ed>>1>=l){
        s=max(s,sum(p<<1,l,r,st,st+ed>>1));
    }
    if(st+ed>>1+1<=r){
        s=max(s,sum(p<<1,l,r,st+ed>>1+1,ed));
    }
    pushup(p);
    return s;
}
int main(){
    freopen("ktt.in","r",stdin);
    freopen("ktt.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]; 
    }
    build(1,1,n);
    while(m--){
        cin>>p;
        if(p==1){
            cin>>x>>y>>z;
            add(1,x,y,1,m,z);
        }else{
            cin>>x>>y;
            cout<<sum(1,x,y,1,m)<<endl;
        }
    }
    return 0;
}