2 条题解
-
0
#include<iostream> #include<cstdio> #define ls (p<<1) #define rs (p<<1|1) #define ll long long using namespace std; const int N=5e5+5; const ll inf=9e18; int n,m; ll a[N]; struct tree { ll max,sum_tag,min_tag,max_tag; }t[N<<2]; void push_up(int p) { t[p].max=max(t[ls].max,t[rs].max); } void push_down(int p,int l,int r) { t[ls].max+=t[p].sum_tag; t[rs].max+=t[p].sum_tag; t[ls].sum_tag+=t[p].sum_tag; t[rs].sum_tag+=t[p].sum_tag; if(t[ls].min_tag<inf)t[ls].min_tag+=t[p].sum_tag; if(t[rs].min_tag<inf)t[rs].min_tag+=t[p].sum_tag; if(t[ls].max_tag>-inf)t[ls].max_tag+=t[p].sum_tag; if(t[rs].max_tag>-inf)t[rs].max_tag+=t[p].sum_tag; t[p].sum_tag=0; t[ls].max=min(t[ls].max,t[p].min_tag); t[rs].max=min(t[rs].max,t[p].min_tag); t[ls].min_tag=min(t[ls].min_tag,t[p].min_tag); t[rs].min_tag=min(t[rs].min_tag,t[p].min_tag); t[ls].max_tag=min(t[ls].max_tag,t[p].min_tag); t[rs].max_tag=min(t[rs].max_tag,t[p].min_tag); t[p].min_tag=inf; t[ls].max=max(t[ls].max,t[p].max_tag); t[rs].max=max(t[rs].max,t[p].max_tag); t[ls].min_tag=max(t[ls].min_tag,t[p].max_tag); t[rs].min_tag=max(t[rs].min_tag,t[p].max_tag); t[ls].max_tag=max(t[ls].max_tag,t[p].max_tag); t[rs].max_tag=max(t[rs].max_tag,t[p].max_tag); t[p].max_tag=-inf; } void build(int p,int l,int r) { t[p].min_tag=inf; t[p].max_tag=-inf; if(l==r) { t[p].max=a[l]; return; } int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); push_up(p); } void update_add(int nl,int nr,int p,int l,int r,ll k) { if(nl<=l&&r<=nr) { t[p].max+=k; t[p].sum_tag+=k; if(t[p].min_tag<inf)t[p].min_tag+=k; if(t[p].max_tag>-inf)t[p].max_tag+=k; return; } push_down(p,l,r); int mid=(l+r)>>1; if(nl<=mid)update_add(nl,nr,ls,l,mid,k); if(mid<nr)update_add(nl,nr,rs,mid+1,r,k); push_up(p); } void update_min(int nl,int nr,int p,int l,int r,ll k) { if(nl<=l&&r<=nr) { t[p].max=min(t[p].max,k); t[p].min_tag=min(t[p].min_tag,k); t[p].max_tag=min(t[p].max_tag,k); return; } push_down(p,l,r); int mid=(l+r)>>1; if(nl<=mid)update_min(nl,nr,ls,l,mid,k); if(mid<nr)update_min(nl,nr,rs,mid+1,r,k); push_up(p); } void update_max(int nl,int nr,int p,int l,int r,ll k) { if(nl<=l&&r<=nr) { t[p].max=max(t[p].max,k); t[p].min_tag=max(t[p].min_tag,k); t[p].max_tag=max(t[p].max_tag,k); return; } push_down(p,l,r); int mid=(l+r)>>1; if(nl<=mid)update_max(nl,nr,ls,l,mid,k); if(mid<nr)update_max(nl,nr,rs,mid+1,r,k); push_up(p); } ll query(int ql,int qr,int p,int l,int r) { if(ql<=l&&r<=qr)return t[p].max; push_down(p,l,r); int mid=(l+r)>>1; ll ans=-inf; if(ql<=mid)ans=max(ans,query(ql,qr,ls,l,mid)); if(mid<qr)ans=max(ans,query(ql,qr,rs,mid+1,r)); return ans; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); build(1,1,n); while(m--) { int q,l,r,k; scanf("%d%d%d",&q,&l,&r); if(q!=4)scanf("%d",&k); if(q==1)update_add(l,r,1,1,n,k); if(q==2)update_min(l,r,1,1,n,k); if(q==3)update_max(l,r,1,1,n,k); if(q==4)printf("%lld\n",query(l,r,1,1,n)); } return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:09:59
#include<iostream> #include<cstdio> #define ls (p<<1) #define rs (p<<1|1) #define ll long long using namespace std; const int N=5e5+5; const ll inf=9e18; int n,m; ll a[N]; struct tree { ll max,sum_tag,min_tag,max_tag; }t[N<<2]; void push_up(int p) { t[p].max=max(t[ls].max,t[rs].max); } void push_down(int p,int l,int r) { t[ls].max+=t[p].sum_tag; t[rs].max+=t[p].sum_tag; t[ls].sum_tag+=t[p].sum_tag; t[rs].sum_tag+=t[p].sum_tag; if(t[ls].min_tag<inf)t[ls].min_tag+=t[p].sum_tag; if(t[rs].min_tag<inf)t[rs].min_tag+=t[p].sum_tag; if(t[ls].max_tag>-inf)t[ls].max_tag+=t[p].sum_tag; if(t[rs].max_tag>-inf)t[rs].max_tag+=t[p].sum_tag; t[p].sum_tag=0; t[ls].max=min(t[ls].max,t[p].min_tag); t[rs].max=min(t[rs].max,t[p].min_tag); t[ls].min_tag=min(t[ls].min_tag,t[p].min_tag); t[rs].min_tag=min(t[rs].min_tag,t[p].min_tag); t[ls].max_tag=min(t[ls].max_tag,t[p].min_tag); t[rs].max_tag=min(t[rs].max_tag,t[p].min_tag); t[p].min_tag=inf; t[ls].max=max(t[ls].max,t[p].max_tag); t[rs].max=max(t[rs].max,t[p].max_tag); t[ls].min_tag=max(t[ls].min_tag,t[p].max_tag); t[rs].min_tag=max(t[rs].min_tag,t[p].max_tag); t[ls].max_tag=max(t[ls].max_tag,t[p].max_tag); t[rs].max_tag=max(t[rs].max_tag,t[p].max_tag); t[p].max_tag=-inf; } void build(int p,int l,int r) { t[p].min_tag=inf; t[p].max_tag=-inf; if(l==r) { t[p].max=a[l]; return; } int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); push_up(p); } void update_add(int nl,int nr,int p,int l,int r,ll k) { if(nl<=l&&r<=nr) { t[p].max+=k; t[p].sum_tag+=k; if(t[p].min_tag<inf)t[p].min_tag+=k; if(t[p].max_tag>-inf)t[p].max_tag+=k; return; } push_down(p,l,r); int mid=(l+r)>>1; if(nl<=mid)update_add(nl,nr,ls,l,mid,k); if(mid<nr)update_add(nl,nr,rs,mid+1,r,k); push_up(p); } void update_min(int nl,int nr,int p,int l,int r,ll k) { if(nl<=l&&r<=nr) { t[p].max=min(t[p].max,k); t[p].min_tag=min(t[p].min_tag,k); t[p].max_tag=min(t[p].max_tag,k); return; } push_down(p,l,r); int mid=(l+r)>>1; if(nl<=mid)update_min(nl,nr,ls,l,mid,k); if(mid<nr)update_min(nl,nr,rs,mid+1,r,k); push_up(p); } void update_max(int nl,int nr,int p,int l,int r,ll k) { if(nl<=l&&r<=nr) { t[p].max=max(t[p].max,k); t[p].min_tag=max(t[p].min_tag,k); t[p].max_tag=max(t[p].max_tag,k); return; } push_down(p,l,r); int mid=(l+r)>>1; if(nl<=mid)update_max(nl,nr,ls,l,mid,k); if(mid<nr)update_max(nl,nr,rs,mid+1,r,k); push_up(p); } ll query(int ql,int qr,int p,int l,int r) { if(ql<=l&&r<=qr)return t[p].max; push_down(p,l,r); int mid=(l+r)>>1; ll ans=-inf; if(ql<=mid)ans=max(ans,query(ql,qr,ls,l,mid)); if(mid<qr)ans=max(ans,query(ql,qr,rs,mid+1,r)); return ans; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); build(1,1,n); while(m--) { int q,l,r,k; scanf("%d%d%d",&q,&l,&r); if(q!=4)scanf("%d",&k); if(q==1)update_add(l,r,1,1,n,k); if(q==2)update_min(l,r,1,1,n,k); if(q==3)update_max(l,r,1,1,n,k); if(q==4)printf("%lld\n",query(l,r,1,1,n)); } return 0; }
- 1
