KTT模板求调，玄棺

你说得对！但是KTT模板求调。

U435624

intr 是阈值

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f
using namespace std;
const int N=100010;
struct zyx{
    int a,b;
}w[N<<2];
int n,m,lazy[N<<2],intr[N<<2],a[N],b[N];
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int inter(zyx x,zyx y){
    int da=x.a-y.a,db=x.b-y.b;
    if((da<=0&&db>=0)||(da>=0&&db<=0))return inf;
    if(da>0)return (da+db-1)/da;
    else return (-da-db+1)/(-da);
}
void pushdown(int u){
    lazy[u*2]+=lazy[u];
    lazy[u*2+1]+=lazy[u];
    w[u*2].b+=lazy[u]*w[u*2].a;
    w[u*2+1].b+=lazy[u]*w[u*2+1].a;
    intr[u*2]-=lazy[u];
    intr[u*2+1]-=lazy[u];
    lazy[u]=0;
}
void pushup(int u){
    if(w[u*2].b>w[u*2+1].b)w[u]=w[u*2];
    else w[u]=w[u*2+1];
    intr[u]=min({intr[u*2],intr[u*2+1],inter(w[u*2],w[u*2+1])});
}
void build(int u,int l,int r){
    intr[u]=inf;
    if(l==r){
        w[u]=(zyx){a[l],b[l]};
        return;
    }
    int mid=(l+r)>>1;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    pushup(u);
}
void rebuild(int u){
    if(intr[u]>0)return;
    pushdown(u);
    rebuild(u*2);
    rebuild(u*2+1);
    pushup(u);
}
void update(int u,int l,int r,int x,int y,int k){
    if(x<=l&&r<=y){
        w[u].b+=w[u].a*k;
        intr[u]-=k;
        lazy[u]+=k;
        rebuild(u);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(u);
    if(x<=mid)update(u*2,l,mid,x,y,k);
    if(y>mid)update(u*2+1,mid+1,r,x,y,k);
    pushup(u);
}
int query(int u,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        return w[u].b;
    }
    int mid=(l+r)>>1;
    pushdown(u);
    int res=0;
    if(x<=mid)res+=query(u*2,l,mid,x,y);
    if(y>mid)res+=query(u*2+1,mid+1,r,x,y);
    return res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        a[i]=read(),b[i]=read();
    }
    build(1,1,n);
    // cout<<"build没炸\n";
    while(m--){
        int op=read(),l=read(),r=read();
        if(op==1){
            int k=read();
            update(1,1,n,l,r,k);
        }
        else{
            cout<<query(1,1,n,l,r)<<'\n';
        }
    }
    return 0;
}