社区讨论

不太明白挂哪里了

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 条回复,欢迎继续交流。

正在加载回复...