Reaper_Osiris @ 2023-07-15 12:00:01
#include<bits/stdc++.h>
#define elif else if
using namespace std;
typedef long long ll;
const ll N=1e6+5;
const ll ll_max=9223372036854775783;//long long 范围内最大的质数
ll a[N],n,ln,rn,sum,q,opt;
//原数组a,长度n,操作区间[ln,rn],操作数sum,命令opt
struct LineTree_max{//最大值线段树
ll l[N<<2],r[N<<2],v[N<<2],ta_add[N<<2],ta_cov[N<<2];
//左右儿子l,r,最大值v,加tag ta_add,赋值tag ta_cov
inline void pdc(ll p){//pushdown_cover
if(ta_cov[p]==ll_max)return;
ll pl=p<<1,pr=p<<1|1;//左右儿子
v[pl]=v[pr]=ta_cov[p];
ta_cov[pr]=ta_cov[pl]=ta_cov[p];
ta_cov[p]=ll_max;
ta_add[p]=ta_add[pl]=ta_add[pr]=0;
}
inline void pda(ll p){//pushdown_add
if(!ta_add[p])return;
ll pl=p<<1,pr=p<<1|1;//左右儿子
v[pl]+=ta_add[p];
ta_add[pl]+=ta_add[p];
v[pr]+=ta_add[p];
ta_add[pr]+=ta_add[p];
ta_add[p]=0;
}
//不想动脑子,就把cover和add的pushdown分开写了
inline ll bu(ll p,ll lu,ll ru){//build
l[p]=lu,r[p]=ru,ta_cov[p]=ll_max;
if(lu==ru)return v[p]=a[lu];
ll mid=(lu+ru)>>1;
return v[p]=max(bu(p<<1,lu,mid),bu(p<<1|1,mid+1,ru));
}
inline ll gs(ll p){//getsum
if(ln>r[p]||rn<l[p])return -ll_max;//防止负值出错
if(ln<=l[p]&&r[p]<=rn) return v[p];//在区间内
pdc(p);
pda(p);//先cover再add
return max(gs(p<<1),gs(p<<1|1));
}
inline void uc(ll p){//update_cover
if(ln<=l[p]&&r[p]<=rn){//在区间内
v[p]=sum;
ta_cov[p]=sum;
ta_add[p]=0;
return;
}
pdc(p);
ll pl=p<<1,pr=p<<1|1;
if(ln<=r[pl])uc(pl);
if(rn>=l[pr])uc(pr);
v[p]=max(v[pl],v[pr]);
}
inline void ua(ll p){//update_add
pdc(p);
if(ln<=l[p]&&r[p]<=rn){//在区间内
v[p]+=sum;
ta_add[p]+=sum;
return;
}
pda(p);
ll pl=p<<1,pr=p<<1|1;
if(ln<=r[pl])ua(pl);
if(rn>=l[pr])ua(pr);
v[p]=max(v[pl],v[pr]);
}
}LT;
int main(){
//freopen("P1253_7.in","r",stdin);
//freopen("P1253_7.ans","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
LT.bu(1,1,n);
for(int i=1;i<=q;i++){
cin>>opt>>ln>>rn;
if(opt==1){
cin>>sum;
LT.uc(1);
}
elif(opt==2){
cin>>sum;
LT.ua(1);
}
elif(opt==3) cout<<LT.gs(1)<<'\n';
}
return 0;
}
调了一个上午,从20分调到60分,人都调麻了。
求各位dalao帮忙调调。
by Epoch_L @ 2023-07-15 13:00:16
为什么你的ua只下传add,uc只下传cover
下传cover为什么要把 add[p] 也清空。
by Reaper_Osiris @ 2023-07-15 17:04:10
屮,蒟蒻一直以为cover覆盖了add就没用了。 原来不能直接覆盖
by Reaper_Osiris @ 2023-07-15 17:06:37
只剩#10还没过了,谢谢佬
@Epoch_L
by Reaper_Osiris @ 2023-07-15 17:14:52
8倍数组过了?!
此贴结。