社区讨论
不太明白挂哪里了
P4513小白逛公园参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mkcj0cxc
- 此快照首次捕获于
- 2026/01/13 19:46 上个月
- 此快照最后确认于
- 2026/01/17 11:50 上个月
CPP
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int n,m;
int a[N];
namespace ste{
struct sgtr{
int l,r;
int sum,ml,mr,mx;
}sgt[4*N];
int lfs(int p){
return p<<1;
}
int rfs(int p){
return (p<<1)|1;
}
bool inr(int p,int l,int r){
return l<=sgt[p].l&&sgt[p].r<=r;
}
void hb(sgtr a,sgtr b,sgtr& c){
c.sum=a.sum+b.sum;
if(a.ml==a.sum){
c.ml=max(a.ml,a.ml+b.ml);
c.ml=max(c.ml,0);
}
if(b.mr==b.sum){
c.mr=max(b.mr,b.mr+a.mr);
c.mr=max(c.mr,0);
}
c.mx=max(a.mx,max(b.mx,a.mr+b.ml));
c.mx=max(c.mx,0);
}
void pushup(int p){
hb(sgt[lfs(p)],sgt[rfs(p)],sgt[p]);
}
void build(int p,int l,int r){
sgt[p].l=l;
sgt[p].r=r;
if(l==r){
sgt[p].sum=a[l];
sgt[p].ml=sgt[p].mr=sgt[p].mx=max(0,a[l]);
// sgt[p].ml=sgt[p].mr=sgt[p].mx=a[l];
return;
}
int mid=(l+r)>>1;
build(lfs(p),l,mid);
build(rfs(p),mid+1,r);
pushup(p);
}
void upd(int p,int pos,int rt){
if(sgt[p].l==sgt[p].r&&sgt[p].l==pos){
sgt[p].sum=rt;
sgt[p].ml=sgt[p].mr=sgt[p].mx=max(0,rt);
return;
}
int mid=(sgt[p].l+sgt[p].r)>>1;
if(pos<=mid){
upd(lfs(p),pos,rt);
}
if(mid<pos){
upd(rfs(p),pos,rt);
}
pushup(p);
}
int query(int p,int l,int r){
if(inr(p,l,r)){
return sgt[p].mx;
}
int res=0;
int mid=(sgt[p].l+sgt[p].r)>>1;
if(l<=mid){
res+=query(lfs(p),l,r);
}
if(mid<r){
res+=query(rfs(p),l,r);
}
return res;
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
ste::build(1,1,n);
while(m--){
int k,a,b;
cin>>k>>a>>b;
if(k==1){
if(a>b) swap(a,b);
cout<<ste::query(1,a,b)<<'\n';
}
if(k==2){
ste::upd(1,a,b);
}
}
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...