Can you answer on these queries III

题面描述

给定长度为N的数列A，以及M条指令 (N≤≤500000, M≤≤100000)，每条指令可能是以下两种之一：

“2 x y”，把 A[x] 改成 y。

“1 x y”，查询区间 [x,y] 中的最大连续子段和，即maxx≤l≤r≤y∑ri=lA[i]maxx≤l≤r≤y∑i=lrA[i]。 对于每个询问，输出一个整数表示答案。

对以上公式进行解释

输入格式

第一行两个整数N,M

第二行N个整数Ai

接下来M行每行3个整数k,x,y，k=1表示查询（此时如果x>y，请交换x,y），k=2表示修改

输出格式

对于每个询问输出一个整数表示答案。

样例

这个题也算是个模板题吧，只是要求的东西比较麻烦，需要思考一下根节点的最大连续子段和是不是左子树的最大和右子树的最大再求个最大呐？猛一听还挺对的，但是我们忘了，在合并完，中间那些数就连了起来，所以我们还需要求一下左子树的最右边和右子树的最左边，sum用来记录子段和，lmax左子树最大连续子段和，rmax右子树最大连续子段和，dat就是我们用来存最终答案的。

与之前模板题不一样的就是回溯时更改值变得难了一点

	t[p].sum=t[p*2].sum+t[p*2+1].sum;
	t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);
	t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax);
	t[p].dat=max(t[p*2].rmax+t[p*2+1].lmax,max(t[p*2].dat,t[p*2+1].dat));

上代码

#include<bits/stdc++.h>
using namespace std;
struct hf
{
	int l,r;
	int dat;
	int lmax;
	int rmax;
	int sum;
}t[2010000];
int a[2010000];
hf ll={0,0,-(1<<30),-(1<<30),-(1<<30),-(1<<30)};
void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r;
	if(l==r)
	{
		t[p].sum=a[l];
		t[p].lmax=a[l];
		t[p].rmax=a[l];
		t[p].dat=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].sum=t[p*2].sum+t[p*2+1].sum;
	t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);
	t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax);
	t[p].dat=max(t[p*2].rmax+t[p*2+1].lmax,max(t[p*2].dat,t[p*2+1].dat));
}
void change(int p,int x,int v)
{
	if(t[p].l==t[p].r)
	{
		t[p].sum=v;
		t[p].lmax=v;
		t[p].rmax=v;
		t[p].dat=v;
		return;
	}
	int mid=(t[p].l+t[p].r)/2;
	if(x<=mid)
	change(p*2,x,v);
	else
	change(p*2+1,x,v);
	t[p].sum=t[p*2].sum+t[p*2+1].sum;
	t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);
	t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax);
	t[p].dat=max(t[p*2].rmax+t[p*2+1].lmax,max(t[p*2].dat,t[p*2+1].dat));
}
hf ask(int p,int l,int r)
{
	if(l>t[p].r||r<t[p].l)
	return ll;
	if(l<=t[p].l&&r>=t[p].r)
	return t[p];
	hf op1,op2,ans;
	op1=ask(p*2,l,r);
	op2=ask(p*2+1,l,r);
	ans.dat=max(op1.dat,max(op2.dat,op1.rmax+op2.lmax));
	ans.lmax=max(op1.lmax,op1.sum+op2.lmax);
	ans.rmax=max(op2.rmax,op2.sum+op1.rmax);
	return ans;
}
int main()
{
	freopen("b.in","r",stdin);
  freopen("b.out","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	build(1,1,n);
	for(int j=1;j<=m;j++)
	{
		int op,x,y;
		cin>>op;
		if(op==2)
		{
			cin>>x>>y;
			change(1,x,y);
		}
		if(op==1)
		{
			cin>>x>>y;
			if(x>y)
			swap(x,y);
			cout<<ask(1,x,y).dat<<endl;
		}
	}
 }