Luogu p4513 xiaobaiguang Park

The question

Two operations are supported for a sequence , One is single point modification , The other is to query the maximum subsegment and .

Algorithm analysis

The complexity of a single maximal subsegment sum is $O(n)$ Grade , But if you ask me many times , Use the original $O(n)$ Method m That complexity $O(nm)$ Toto explosion . In this case, the segment tree can be used to maintain the maximum subsegment sum of an interval .

specific working means

1. For each tree node , Need to have an interval and $w$, The largest subsegment of an interval and $v$, Starting with the left and right endpoints of the sequence $lw$ and $rw$. The first two are easy to understand , But why should the last two start with the left endpoint or the right endpoint ？
   In fact, for the parent node , When inheriting from a child node , If two child nodes （ That is, two segment subsequence ） The largest sub segment of and the point without boundary , In fact, even if you don't add the following answer, it doesn't have to be $$ans=\max (a_{LeftSonTrees}.w,b_{RightSonTrees}.w)$$ We need to consider that subsequences of two end intervals can be added together , At this time, we can take the $ans$ Then compare the size $$ans=\max (ans,a_{LeftSonTrees}.rw+b_{RightSonTrees}.lw)$$ It means that I can take the maximum sub segment of the left subtree that starts with the right endpoint and add the maximum sub segment of the right subtree that starts with the left endpoint , In this way, we can find the maximum sum of subsequences .
2. How do you get it $lw$ and $rw$ The value of ？ All we need to do is $pushup$ The function is slightly modified .
   For interval sum, just add it directly .
   about $lw$ Consider taking $\max (a_{LeftSonTrees}.lw,a_{LeftSonTrees}.v+b_{RightSonTrees}.lw)$, Represents either the sum of the largest sub segments of the left subtree starting with the left endpoint , Or it will be $lw$ The sequence extends directly to the right subtree . Empathy $rw$ You can do the same .
   Finally obtain $$w=\max (\max (a_{LeftSonTrees}.w,b_{RightSonTrees}.w),a_{LeftSonTrees}.rw+b_{RightSonTrees}.lw)$$
3. The update operation is similar to the naive segment tree .
4. The query operation cannot be used directly $w$ To compare the size , We are going to return a node instead of a value .
   When the interval of a node is covered by the queried interval , Just go back to the node .
   When the interval only involves one of the nodes （ Notice that it's a ） In the interval , Query the child node directly .
   When two child nodes are involved , You can create a new answer node , It is responsible for storing the child answer nodes returned from the left and right child nodes , Then, according to the two sub answer nodes, the answer nodes are re $pushup$ At a time can be . Finally, return to the answer node . Finally, output the top answer node $w$ that will do .
5. matters needing attention ： The shortest subsequence is 1, So for leaf nodes, you need to assign all their values to the value of the position of the whole sequence .

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=5e5+5;
int a[maxn],n,m;
struct node{
    
	int l,r;
	int v,w,lw,rw;
}t[maxn<<2];
inline void pushup(int k)
{
    
	t[k].v=t[k<<1].v+t[k<<1|1].v;
	t[k].lw=max(t[k<<1].v+t[k<<1|1].lw,t[k<<1].lw);
	t[k].rw=max(t[k<<1].rw+t[k<<1|1].v,t[k<<1|1].rw);
	t[k].w=max(max(t[k<<1].w,t[k<<1|1].w),t[k<<1].rw+t[k<<1|1].lw);
}
inline void build(int k,int l,int r)
{
    
	t[k].l=l,t[k].r=r;
	if(l==r){
    
		t[k].v=t[k].w=t[k].lw=t[k].rw=a[l];
		return;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
inline void update(int k,int x,int y)
{
    
	int l=t[k].l,r=t[k].r;
	if(l==r){
    
		t[k].v=t[k].w=t[k].lw=t[k].rw=y;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid)update(k<<1,x,y);
	else update(k<<1|1,x,y);
	pushup(k);
}
inline node query(int k,int l,int r)
{
    
	int x=t[k].l,y=t[k].r;
	if(l<=x&&y<=r)return t[k];
	int mid=x+y>>1;
	if(r<=mid)return query(k<<1,l,r); 
	else if(l>mid)return query(k<<1|1,l,r);
	else{
    
		node a=query(k<<1,l,r),b=query(k<<1|1,l,r),ans;
		ans.v=a.v+b.v;
		ans.lw=max(a.v+b.lw,a.lw);
		ans.rw=max(b.v+a.rw,b.rw);
		ans.w=max(max(a.w,b.w),a.rw+b.lw);
		return ans;
	}
}
int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
    
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
    
		int op,l,r;
		cin>>op>>l>>r;
		if(op==1){
    
			if(l>r)swap(l,r);
			node ans=query(1,l,r);
			cout<<ans.w<<"\n";
		}
		else{
    
			update(1,l,r);
		}
	}
	return 0;
}