洛谷 - P4513 小白逛公园

传送门：洛谷 - P4513

题目描述

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

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

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

输入描述

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

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

输出描述

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

思路分析

很明显的最大区间连续子段和，那要怎么维护呢

• sum表示区间和
• ls表示连接左端点的最大连续子段和
• rs表示连接右端点的最大连续子段和
• mx表示区间最大连续子段和

具体操作看代码

样例输入

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

样例输出

2
-1

AC代码

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=1e6+10;

struct node {
    int l,r,mid;
    int sum,ls,rs,mx;
} tree[N<<2];

int a[N];

void pushup(int x) {
    tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;
    tree[x].ls=max(tree[x*2].ls,tree[x*2].sum+tree[x*2+1].ls);
    tree[x].rs=max(tree[x*2+1].rs,tree[x*2+1].sum+tree[x*2].rs);
    tree[x].mx=max(tree[x*2].rs+tree[x*2+1].ls,max(tree[x*2].mx,tree[x*2+1].mx));
}

void build(int x,int l,int r) {
    tree[x].l=l;
    tree[x].r=r;
    tree[x].mid=l+r>>1;
    if(l==r) {
        tree[x].ls=a[l];
        tree[x].mx=a[l];
        tree[x].sum=a[l];
        tree[x].rs=a[l];
        return ;
    }
    int mid=tree[x].mid;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    pushup(x);
}

void update(int x,int pos,int v) {
    if(tree[x].l==tree[x].r && tree[x].l==pos) {
        tree[x].ls=v;
        tree[x].mx=v;
        tree[x].sum=v;
        tree[x].rs=v;
        return ;
    }
    int mid=tree[x].mid;
    if(pos<=mid)
        update(x*2,pos,v);
    else
        update(x*2+1,pos,v);
    pushup(x);
}

node query(int x,int l,int r) {
    if(l<=tree[x].l && tree[x].r<=r) {
        return tree[x];
    }
    int mid=tree[x].mid;
    if(r<=mid) {
        return query(x*2,l,r);
    } else if(l>mid) {
        return query(x*2+1,l,r);
    } else {
        node lson=query(x*2,l,r);
        node rson=query(x*2+1,l,r);
        node ans;
        ans.sum=lson.sum+rson.sum;
        ans.ls=max(lson.ls,lson.sum+rson.ls);
        ans.rs=max(rson.rs,rson.sum+lson.rs);
        ans.mx=max(lson.rs+rson.ls,max(lson.mx,rson.mx));
        return ans;
    }
}


int main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)scanf("%d",&a[i]);
    build(1,1,n);
    while(m--) {
        int o,l,r;
        scanf("%d%d%d",&o,&l,&r);
        if(o==1) {
            if(l>r)swap(l,r);
            printf("%d\n",query(1,l,r).mx);
        } else {
            update(1,l,r);
        }
    }

    return 0;
}