问题描述

[LG-SP1716](https://www.luogu.org/problem/SP1716]

---

题解

GSS 系列的第三题，在第一题的基础上带单点修改。

第一题题解传送门

在第一题的基础上，增加一个单点修改就完事了。

---

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();

	if(ch=='-') ch=getchar(),fh=-1;

	else fh=1;

	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	x*=fh;

}

const int maxn=50007;

#define lfc (x<<1)

#define rgc ((x<<1)|1)

#define mid ((l+r)>>1)

int n;

int val[maxn<<2],lf[maxn<<2],rg[maxn<<2];

int sum[maxn<<2];

int a[maxn];

void pushup(int x){

	sum[x]=sum[lfc]+sum[rgc];

	lf[x]=max(lf[lfc],sum[lfc]+lf[rgc]);

	rg[x]=max(rg[rgc],sum[rgc]+rg[lfc]);

	val[x]=max(max(val[lfc],val[rgc]),rg[lfc]+lf[rgc]);

}

void build(int x,int l,int r){

	if(l==r){

		sum[x]=val[x]=lf[x]=rg[x]=a[l];

		return;

	}

	build(lfc,l,mid);build(rgc,mid+1,r);

	pushup(x);

}

const int INF=0x3f3f3f3f;

int L,R,need;

struct node{

	int val,lf,rg,sum;

};

node query(int x,int l,int r){

	if(L<=l&&r<=R) return (node){val[x],lf[x],rg[x],sum[x]};

	if(L>mid) return query(rgc,mid+1,r);

	if(R<=mid) return query(lfc,l,mid);

	node res,s1=query(lfc,l,mid),s2=query(rgc,mid+1,r);

	res.sum=s1.sum+s2.sum;

	res.val=max(max(s1.val,s2.val),s1.rg+s2.lf);

	res.lf=max(s1.lf,s1.sum+s2.lf);

	res.rg=max(s2.rg,s2.sum+s1.rg);

	return res;

}

int op;

void change(int x,int l,int r){

	if(l==r){

		val[x]=lf[x]=sum[x]=rg[x]=need;return;

	}

	if(L<=mid) change(lfc,l,mid);

	else change(rgc,mid+1,r);

	pushup(x);

}

int main(){

	read(n);

	for(int i=1;i<=n;i++) read(a[i]);

	build(1,1,n);

	int T;read(T);

	while(T--){

		read(op);read(L);read(R);

		if(op==1) printf("%d\n",query(1,1,n).val);

		else{

			need=R;

			change(1,1,n);

		}

	}

	return 0;

}