hit oj 2687 Candy (线段树动态维护最大连续子段)
题意:给出n个数,m个修改,每次修改后询问整个区间的最大连续子段。
思路:考虑一段区间,分成左右两个子区间,这段区间的最大子段有三种情况:只在左区间中,只在右区间中,既在左区间中又在右区间中。前两种很好维护,对于后一种,我们新增加线段树的两个域,mxl,mxr,分别表示一个区间中包含左端点在的最大字段和(也就是最大前缀和),和一个区间中包含右端点在的最大子段和(也就是最大后缀和),然后对于最大子段既在左区间又在右区间的情况,只需要合并【左区间的最大后缀和 】和【右区间的最大前缀和】就好。
关于一个区间最大前缀和的维护,取该区间的左区间的最大前缀和和【该区间的左区间和】+【该区间的右区间的最大前缀和】的最大值。
最大后缀和同理。
这是一种很经典的做法,注意体会。
1A
/* ***********************************************
Author :111qqz
Created Time :Fri 16 Sep 2016 04:01:49 AM CST
File Name :code/hitoj/2687.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7int n,m;
8struct
9{
10 int mx;
11 int mxr;
12 int mxl;
13 int sum;
14}tree[N<<2];
15void PushUp( int rt)
16{
17 tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
18 if (tree[rt<<1].mxr>0&&tree[rt<<1|1].mxl>0) //区间合并
19 tree[rt].mx = tree[rt<<1].mxr + tree[rt<<1|1].mxl;
20 else tree[rt].mx = max(tree[rt<<1].mxr,tree[rt<<1|1].mxl);
21 tree[rt].mx = max(tree[rt].mx,max(tree[rt<<1].mx,tree[rt<<1|1].mx));
22 tree[rt].mxl = max(tree[rt<<1].mxl,tree[rt<<1|1].mxl+tree[rt<<1].sum);
23 tree[rt].mxr = max(tree[rt<<1|1].mxr,tree[rt<<1].mxr+tree[rt<<1|1].sum);
24}
25void build(int l,int r,int rt)
26{
27 if (l==r)
28 {
29 int x;
30 scanf("%d",&x);
31 tree[rt].mx = tree[rt].mxl = tree[rt].mxr = tree[rt].sum = x;
32 return;
33 }
34 int m = (l+r)>>1;
35 build(lson);
36 build(rson);
37 PushUp(rt);
38}
39void update( int p,int sc,int l,int r,int rt)
40{
41 if (l==r)
42 {
43 tree[rt].mx = tree[rt].mxl = tree[rt].mxr = tree[rt].sum = sc;
44 return;
45 }
46 int m = (l+r)>>1;
47 if (p<=m) update(p,sc,lson);
48 else update(p,sc,rson);
49 PushUp(rt);
50}
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("code/in.txt","r",stdin);
5 #endif
6 while (~scanf("%d%d",&n,&m))
7 {
8 build(1,n,1);
9 while (m--)
10 {
11 int p,x;
12 scanf("%d%d",&p,&x);
13 update(p,x,1,n,1);
14 printf("%d\n",tree[1].mx);
15 }
16 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}