P4513 小白逛公园
XichenOC
·
·
题解
P4513 小白逛公园
题目翻译：
给定一个长度为n初始序列，并进行m次询问，求一个区间类的最大连续子序列的大小，或者单点修改。
思路：
看到单点修改和区间查询可以很容易想到线段树，那如何用线段树来维护最大连续子序列。我们考虑给线段树维护以下参数：
lm,rm,sum,mx
>$1.$一个区间的从左的最大连续序列可能是它左儿子的从左开始的最大连续序列，也有可能是最儿子的和在加上右儿子的从左开始的最大连续序列,而右边同理:
>$$$tr[p].lm=max(tr[lc].lm,tr[lc].sum+tr[rc].lm);$$$
>$$$tr[p].rm=max(tr[rc].rm,tr[rc].sum+tr[lc].rm);$$$
>
>---
>$2.$若一个区间的最大连续子序列可以是它左儿子的或者右儿子的，但也有可能是做儿子的右最长加上右儿子的左最长，因此关系为：
>$$$tr[p].mx=max(max(tr[lc].mx,tr[rc].mx),tr[rc].lm+tr[lc].rm);$$$
>
>---
>$3.$和就不用说，就是左右儿子和之和：
>$$$tr[p].sum=tr[lc].sum+tr[rc].sum;$$$
这样就得到了根节点和左右儿子的关系：
```cpp
void push_up(int p){
tr[p].sum=tr[lc].sum+tr[rc].sum;
tr[p].lm=max(tr[lc].lm,tr[lc].sum+tr[rc].lm);
tr[p].rm=max(tr[rc].rm,tr[rc].sum+tr[lc].rm);
tr[p].mx=max(max(tr[lc].mx,tr[rc].mx),tr[rc].lm+tr[lc].rm);
}
```
后面就不用说，普通的单点修改和区间查询，~~感觉蓝有点过头了~~
```cpp
#include<bits/stdc++.h>
#define int long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N=5e5+10;
struct Tree{
int lm,rm,mx,sum;
}tr[N*4];
int a[N];
void push_up(int p){
tr[p].sum=tr[lc].sum+tr[rc].sum;
tr[p].lm=max(tr[lc].lm,tr[lc].sum+tr[rc].lm);
tr[p].rm=max(tr[rc].rm,tr[rc].sum+tr[lc].rm);
tr[p].mx=max(max(tr[lc].mx,tr[rc].mx),tr[rc].lm+tr[lc].rm);
}
void build(int p,int l,int r){
if(l==r){
tr[p].lm=tr[p].rm=tr[p].mx=tr[p].sum=a[l];
return;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
push_up(p);
}
Tree query(int p,int l,int r,int ll,int rr){
if(ll<=l&&r<=rr){
return tr[p];
}
int mid=(l+r)>>1;
if(ll>mid)return query(rc,mid+1,r,ll,rr);
else{
if(rr<=mid)return query(lc,l,mid,ll,rr);
else{
Tree res,lt=query(lc,l,mid,ll,rr),rt=query(rc,mid+1,r,ll,rr);
res.lm=max(lt.lm,lt.sum+rt.lm);
res.rm=max(rt.rm,rt.sum+lt.rm);
res.mx=max(max(lt.mx,rt.mx),lt.rm+rt.lm);
res.sum=lt.sum+rt.sum;
return res;
}
}
}
void update(int p,int l,int r,int k,int num){
if(l==r){
//cout<<l<<endl;
tr[p].lm=tr[p].rm=tr[p].mx=tr[p].sum=num;
return;
}
int mid=(l+r)>>1;
if(k<=mid)update(lc,l,mid,k,num);
else update(rc,mid+1,r,k,num);
push_up(p);
}
signed main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
while(m--){
int k;
cin>>k;
if(k==1){
int l,r;
cin>>l>>r;
if(l>r)swap(l,r);
cout<<query(1,1,n,l,r).mx<<endl;
}
if(k==2){
int k,num;
cin>>k>>num;
update(1,1,n,k,num);
}
}
}
```
[**线段树讲解**](https://www.luogu.com.cn/article/ojh62kc0)