本文主要是介绍Vijos 小白逛公园 线段树加DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。
一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择**连续**的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。
那么，就请你来帮小白选择公园吧。
格式
输入格式
第一行，两个整数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≤500 000，1≤M≤100 000，所有打分都是绝对值不超过1000的整数。
输出格式
小白每出去玩一次，都对应输出一行，只包含一个整数，表示小白可以选出的公园得分和的最大值。
样例1
样例输入1
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 2 3
样例输出1
2
-1
限制
各个测试点2s
1 /* 2 left表示从左端点向右能达到的最大值 3 right表示从右端点到右所能达到的最大值 4 maxv就是我们要求的 即整个区间中能达到的最大连续和值 5 sum自然就是所有区间内所有数的和了 6 7 第一个sum不言而喻地球人都知道 8 第二个left我们可以知道是要从左端点向右 9 那么我们分治分成两半 一定有要么是左半端点向右延伸没有到达中点 10 要么是左端端点延伸到达了右部分 所以这个时候肯定就是选取了全部的左边加上右端的left 11 第三个也是一样的道理咯 这里就不赘说了 12 第四个maxv我们就是和O(nlogn)算法的思路一样了 13 我们知道一个最大连续和的子序列 要么是左半段的最大和 要么就是右半段的最大和 14 要么就是横跨左右的最大和 15 那么我们对应的就是tree[o<<1].maxv tree[o<<1|1].maxv tree[o<<1].right+tree[o<<1|1].left 16 然后就取下最大值就好了 17 */ 18 #include<iostream> 19 #include<cstdio> 20 #include<algorithm> 21 #include<cstring> 22 using namespace std; 23 24 const int MAXN=500010; 25 struct node 26 { 27 int bj; 28 int left,right,maxv,sum; 29 }tree[MAXN<<2]; 30 int n,m; 31 32 void renew(int o) 33 { 34 tree[o].sum=tree[o<<1].sum+tree[o<<1|1].sum; 35 tree[o].left=max(tree[o<<1].left,tree[o<<1].sum+tree[o<<1|1].left); 36 tree[o].right=max(tree[o<<1|1].right,tree[o<<1|1].sum+tree[o<<1].right); 37 tree[o].maxv=max(tree[o<<1].right+tree[o<<1|1].left,max(tree[o<<1].maxv,tree[o<<1|1].maxv)); 38 } 39 40 void change(int o,int l,int r,int a,int c) 41 { 42 if(l==r) 43 { 44 tree[o].bj=o; 45 tree[o].left=tree[o].right=tree[o].maxv=tree[o].sum=c; 46 return; 47 } 48 int mid=(l+r)>>1; 49 if(a<=mid) 50 change(o<<1,l,mid,a,c); 51 else 52 change(o<<1|1,mid+1,r,a,c); 53 renew(o); 54 } 55 56 node query(int o,int l,int r,int a,int b) 57 { 58 if(a<=l&&b>=r) return tree[o]; 59 int mid=(l+r)>>1; 60 if(b<=mid) 61 return query(o<<1,l,mid,a,b); 62 else if(a>mid) 63 return query(o<<1|1,mid+1,r,a,b); 64 else 65 { 66 node res,res1,res2; 67 res1=query(o<<1,l,mid,a,b); 68 res2=query(o<<1|1,mid+1,r,a,b); 69 res.sum=res1.sum+res2.sum; 70 res.left=max(res1.left,res1.sum+res2.left); 71 res.right=max(res2.right,res2.sum+res1.right); 72 res.maxv=max(res1.right+res2.left,max(res1.maxv,res2.maxv)); 73 return res; 74 } 75 } 76 77 int main() 78 { 79 int x,op,a,b; 80 cin>>n>>m; 81 for(int i=1;i<=n;i++) 82 { 83 cin>>x; 84 change(1,1,n,i,x); 85 } 86 while(m--) 87 { 88 cin>>op>>a>>b; 89 if(op==1) 90 { 91 if(a>b) 92 swap(a,b); 93 printf("%d\n",query(1,1,n,a,b).maxv); 94 } 95 else 96 change(1,1,n,a,b); 97 } 98 return 0; 99 }
这篇关于Vijos 小白逛公园 线段树加DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
