luogu P4513 小白逛公园

题目大意

需要一种数据结构,支持以下两种操作:

1. 单点修改
2. 区间求最大连续子段和

Sol

很容易想到线段树
首先我们要维护一个区间和\(sum\)
但是只用\(sum\)不能维护区间最大连续子段和
发现最大连续子段和可以从以下几种方式转移:

1. 左子区间从右开始最大连续和+右子区间从左开始的最大连续和
2. 左子区间最大连续子段和
3. 右子区间最大连续子段和

所以我们需要额外维护:

1. \(lmax\)表示当前区间从左开始最大连续和
2. \(rmax\)表示当前区间从右开始最大连续和

考虑\(lmax\)如何转移:

1. 从左子区间的\(lmax\)转移
2. 左子区间和+右子区间的\(lmax\)

\(rmax\)同理

注意，在查询时，如果跨越两边，由于所给区间不会完全被某两个区间包裹，我们需要在递归返回过程中重新计算贡献
（也就是返回一个 Node）

Code

#include <cstdio>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 5e5+10;
const LL INF = 0x3f3f3f3f3f3f3f3f;struct Node {int l , r;LL sum;LL lmax , rmax , dmax;
};int n , m;
int a[N];
Node tr[N*4];void pushup(int x) {tr[x].sum = tr[x<<1].sum + tr[x<<1|1].sum;tr[x].lmax = max(tr[x<<1].lmax , tr[x<<1].sum+tr[x<<1|1].lmax);tr[x].rmax = max(tr[x<<1|1].rmax , tr[x<<1|1].sum+tr[x<<1].rmax);tr[x].dmax = max(tr[x<<1].rmax+tr[x<<1|1].lmax , max(tr[x<<1].dmax , tr[x<<1|1].dmax));
}void build(int x , int l , int r) {tr[x] = {l , r , 0 , 0 , 0 , 0};if(l == r) {tr[x] = {l , r , a[l] , a[l] , a[l] , a[l]};return ;}int mid = (l+r) >> 1;build(x<<1 , l , mid);build(x<<1|1 , mid+1 , r);pushup(x);
}void modify(int x , int l , LL k) {if(tr[x].l == tr[x].r) {tr[x] = {tr[x].l , tr[x].r , k , k , k , k};return;}int mid = (tr[x].l + tr[x].r) >> 1;if(l <= mid) modify(x<<1 , l , k);else modify(x<<1|1 , l , k);pushup(x);
}Node query(int x , int l , int r) {if(l <= tr[x].l && tr[x].r <= r) return tr[x];int mid = (tr[x].l+tr[x].r) >> 1;if(l <= mid && mid < r) {Node t , ls = query(x<<1 , l , r) , rs = query(x<<1|1 , l , r);t.sum = ls.sum + rs.sum;t.lmax = max(ls.lmax , ls.sum + rs.lmax);t.rmax = max(rs.rmax , rs.sum + ls.rmax);t.dmax = max(max(ls.dmax , rs.dmax) , ls.rmax+rs.lmax);return t;}if(r <= mid) return query(x<<1 , l , r);if(l > mid) return query(x<<1|1 , l , r);return Node();
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);cin >> n >> m;for(int i = 1 ; i <= n ; i ++)cin >> a[i];build(1 , 1 , n);while(m --) {int opt , x , y;cin >> opt >> x >> y;if(opt & 1) {if(x > y) swap(x , y);cout << query(1 , x , y).dmax << '\n';} else {modify(1 , x , y);}}return 0;
}

闲话

事实上，这个题被丢在我的题堆里两个月了