小白逛公园
题目背景
小新经常陪小白去公园玩,也就是所谓的遛狗啦…
题目描述
在小新家附近有一条“公园路”,路的一边从南到北依次排着 $n$ 个公园,小白早就看花了眼,自己也不清楚该去哪些公园玩了。
一开始,小白就根据公园的风景给每个公园打了分。小新为了省事,每次遛狗的时候都会事先规定一个范围,小白只可以选择第 $a$ 个和第 $b$ 个公园之间(包括 $a, b$ 两个公园)选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时,由于一些公园的景观会有所改变,所以,小白的打分也可能会有一些变化。
那么,就请你来帮小白选择公园吧。
输入格式
第一行,两个整数 $n$ 和 $m$,分别表示表示公园的数量和操作(遛狗或者改变打分)总数。
接下来 $n$ 行,每行一个整数,依次给出小白开始时对公园的打分。
接下来 $m$ 行,每行三个整数。其中第一个整数 $k$ 为 $1$ 或 $2$。
- $k=1$ 表示,小新要带小白出去玩,接下来的两个整数 $a$ 和 $b$ 给出了选择公园的范围 $(1 \le a,b \le n)$。测试数据可能会出现 $a > b$ 的情况,需要进行交换;
- $k=2$ 表示,小白改变了对某个公园的打分,接下来的两个整数 $p$ 和 $s$,表示小白对第 $p$ 个公园的打分变成了 $s(1\le p\le N)$。
输出格式
小白每出去玩一次,都对应输出一行,只包含一个整数,表示小白可以选出的公园得分和的最大值。
样例 #1
样例输入 #1
5 3
1
2
-3
4
5
1 2 3
2 2 -1
1 2 3
样例输出 #1
2
-1
提示
数据规模与约定
对于 $100\%$ 的数据,$1 \le n \le 5 \times 10^5$,$1 \le m \le 10^5$,所有打分都是绝对值不超过 $1000$ 的整数。
这道题
用分治的树形dp线段树就好了
思路:
这道题,北海没有WA这个讨厌的单细胞生物准备用动态修改+区间最大子段和qwq
那么问题来了:
最大子段和怎么维护捏?
首先,我想到就鲁莽地设置状态为:”(tree[pos])表示本区间的最大子段和。“但是显然的是,我好像有那个大病
因为这种状态是不支持上推的,它的准确程度无法保证,因为可能会有最大子段和是跨过这个区间的中点的,所以不能以中点分成两个son来做qaq
那么办呢?
当然是–
把这道题丢进垃圾桶里
敲黑板
我们需要河狸地设置一个或多个状态,使得这些状态的父子关系可以平滑向上更新。
那么我们考虑这么设:
设置:
\(tree[pos]\)表示当前节点表示区间的最大子段和
\(lmax[pos]\)表示当前节点表示区间一定包含左端点的最大子段和
\(rmax[pos]\)表示当前节点表示区间一定包含右端点的最大子段和
\(sum[pos]\)表示当前节点表示区间的总和
那问题又来了
为什么这么设置呢?
因为,我们要把这道题
丢进垃圾桶里
敲黑板*2
仍然回到上面讲到的问题:为什么不能只设(tree[pos])表示答案呢?因为可能存在最大子段和的区间横跨中点的情况出现。那么如何才能把这种情况也包含进去呢?简单啊,把这个区间拆开就好了,于是就有了以上(lmax,rmax)的状态。
于是,我们可以$\Huge\color{#D700F}{丝滑}$的转移:
设\(lson/rson\)为当前节点\(pos\)的左右儿子,有:
\(tree[pos]=\max(tree[lson],tree[rson],lmax[rson]+rmax[lson])\)
然后我们还需要考虑如何维护\(lmax[],rmax[]\),也很~~简单~~:
\(lmax[pos]=\max(sum[lson]+lmax[rson],lmax[lson])\)
\(rmax[pos]=\max(rmax[rson],rmax[lson]+sum[rson])\)
那么问题又又来了
这道题该如何实现呢?
首先,我们应该把这道题
丢进垃圾桶里
Code(C++)
#include<cstdio>
#include<algorithm>
#define lson pos<<1
#define rson pos<<1|1
using namespace std;
const int maxn=5*1e5+10;
int n,m;
int w[maxn];
struct node
{
int tree,lmax,rmax,sum;
}a[maxn<<2];
void pushup(int pos)
{
a[pos].sum=a[lson].sum+a[rson].sum;
a[pos].lmax=max(a[lson].lmax,a[lson].sum+a[rson].lmax);
a[pos].rmax=max(a[rson].rmax,a[rson].sum+a[lson].rmax);
a[pos].tree=max(max(a[lson].tree,a[rson].tree),a[lson].rmax+a[rson].lmax);
}
void build(int pos,int l,int r)
{
int mid=(l+r)>>1;
if(l==r)
{
a[pos].tree=a[pos].lmax=a[pos].rmax=a[pos].sum=w[l];
return;
}
build(lson,l,mid);
build(rson,mid+1,r);
pushup(pos);
}
void update(int pos,int l,int r,int x,int k)
{
int mid=(l+r)>>1;
if(l==r)
{
a[pos].tree=a[pos].lmax=a[pos].rmax=a[pos].sum=k;
return;
}
if(x<=mid)
update(lson,l,mid,x,k);
else
update(rson,mid+1,r,x,k);
pushup(pos);
}
node query(int pos,int l,int r,int x,int y)
{
node ret;
int mid=(l+r)>>1;
if(x<=l && r<=y)
return a[pos];
else if(y<=mid)
ret=query(lson,l,mid,x,y);
else if(x>mid)
ret=query(rson,mid+1,r,x,y);
else
{
node p=query(lson,l,mid,x,y);
node q=query(rson,mid+1,r,x,y);
ret.sum=p.sum+q.sum;
ret.lmax=max(p.lmax,p.sum+q.lmax);
ret.rmax=max(q.rmax,q.sum+p.rmax);
ret.tree=max(max(p.tree,q.tree),p.rmax+q.lmax);
}
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
build(1,1,n);
while(m--)
{
int k,x,y;
scanf("%d%d%d",&k,&x,&y);
if(k==1)
{
if(x>y)
swap(x,y);
printf("%d\n",query(1,1,n,x,y).tree);
}
else
update(1,1,n,x,y);
}
return 0;
}
你以为这就完事了?
我们要把这道题
从垃圾桶里捡出来
然后:
再丢进垃圾桶里
你以为这就完事了
nonono
我们还要把这道题:
从垃圾桶里捡出来
再丢到
垃圾桶里
之后就用洛谷评测姬测一下就ok啦
完结撒花~
礼貌:“你垃姬桶吗”
qaq
#
垃圾桶:还我版权。