线段树区间最大连续区间和模板

r囧r小猫 2021-11-05 05:48 384阅读 0赞

### 题目背景 ###

小新经常陪小白去公园玩，也就是所谓的遛狗啦…

### 题目描述 ###

在小新家附近有一条“公园路”，路的一边从南到北依次排着nn个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。

一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第aa个和第bb个公园之间（包括aa、bb两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。

那么，就请你来帮小白选择公园吧。

### 输入格式 ###

第一行，两个整数NN和MM，分别表示表示公园的数量和操作（遛狗或者改变打分）总数。  
接下来NN行，每行一个整数，依次给出小白 开始时对公园的打分。  
接下来MM行，每行三个整数。第一个整数KK，11或22。

*  K=1K=1表示，小新要带小白出去玩，接下来的两个整数aa和bb给出了选择公园的范围（1≤a,b≤N1≤a,b≤N）。测试数据可能会出现a>ba>b的情况，需要进行交换；
 *  K=2K=2表示，小白改变了对某个公园的打分，接下来的两个整数pp和ss，表示小白对第pp个公园的打分变成了ss（1≤p≤N1≤p≤N）。  
    其中，1≤N≤500 0001≤N≤500000，1≤M≤100 0001≤M≤100000，所有打分都是绝对值不超过10001000的整数。

### 输出格式 ###

小白每出去玩一次，都对应输出一行，只包含一个整数，表示小白可以选出的公园得分和的最大值。

### 输入输出样例 ###

**输入 \#1**复制

5 3
    1 2 -3 4 5
    1 2 3
    2 2 -1
    1 2 3

**输出 \#1**复制

2
    -1

#include<bits/stdc++.h>
    using namespace std;
    #define LL long long 
    const int M=5e5+50;
    int n,m,d[M];
    struct Node{
    	int l,r;
    	LL lm,rm,mm,sum;
    }t[M*4];
    void matain(int k){
    	t[k].mm=max(max(t[k*2].mm,t[k*2+1].mm),t[k*2].rm+t[k*2+1].lm);
    	t[k].lm=max(t[k*2].lm,t[k*2].sum+t[k*2+1].lm);
    	t[k].rm=max(t[k*2+1].rm,t[k*2].rm+t[k*2+1].sum);
    	t[k].sum=t[k*2].sum+t[k*2+1].sum;
    }
    void build(int k,int l,int r){
    	t[k].l=l;
    	t[k].r=r;
    	if(l==r){
    		t[k].lm=t[k].rm=t[k].mm=t[k].sum=d[l];
    		return ;
    	}
    	int mid=(l+r)>>1;
    	build(k*2,l,mid);
    	build(k*2+1,mid+1,r);
    	matain(k);
    }
    void update(int k,int v,int w){
    	if(t[k].l==t[k].r){
    		t[k].lm=t[k].rm=t[k].mm=t[k].sum=w;
    		return ;
    	}
    	int mid=(t[k].l+t[k].r)>>1;
    	if(v<=mid)update(k*2,v,w);
    	else update(k*2+1,v,w);
    	matain(k);
    }
    Node query(int k,int l,int r){ 
    	if(l<=t[k].l&&t[k].r<=r)return t[k];
    	int mid=(t[k].l+t[k].r)>>1;
    	if(r<=mid)return query(k*2,l,r);
    	else if(mid<l)return query(k*2+1,l,r);
    	else{
    		Node t0,t1=query(k*2,l,r),t2=query(k*2+1,l,r);
    		t0.mm=max(max(t1.mm,t2.mm),t1.rm+t2.lm);
    		t0.lm=max(t1.lm,t2.lm+t1.sum);
    		t0.rm=max(t2.rm,t1.rm+t2.sum);
    		t0.sum=t1.sum+t[2].sum;
    		return t0;
    	}
    }
    int main(){
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;i++)scanf("%d",&d[i]);
    	build(1,1,n);
    		for(int op,x,y,i=1;i<=m;i++){
    		scanf("%d%d%d",&op,	&x,&y);
    		if(op==1)	printf("%lld\n",query(1,min(x,y),max(x,y)).mm);
    		else update(1,x,y);
    	}
    	return 0;
    }