比赛 |
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;
}