BZOJ 1756: Vijos1083 小白逛公园 （线段树维护单点修改区间查询最大子段和）
1756: Vijos1083 小白逛公园
Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1078 Solved: 353 [Submit][Status][Discuss]
Description
小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。 一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。 那么，就请你来帮小白选择公园吧。
Input
第一行，两个整数N和M，分别表示表示公园的数量和操作（遛狗或者改变打分）总数。 接下来N行，每行一个整数，依次给出小白 开始时对公园的打分。 接下来M行，每行三个整数。第一个整数K，1或2。K=1表示，小新要带小白出去玩，接下来的两个整数a和b给出了选择公园的范围（1≤a,b≤N）；K=2表示，小白改变了对某个公园的打分，接下来的两个整数p和s，表示小白对第p个公园的打分变成了s（1≤p≤N）。 其中，1≤N≤500 000，1≤M≤100 000，所有打分都是绝对值不超过1000的整数。
Output
小白每出去玩一次，都对应输出一行，只包含一个整数，表示小白可以选出的公园得分和的最大值。
Sample Input
5 3 1 2 -3 4 5 1 2 3 2 2 -1 1 2 3
Sample Output
2 -1
题意：中文题面，不多说。
思路：关于维护最大子段和的问题，做法同
但是和上面这道题不同的是，每次询问的是某个区间的最大字段和，而不是整个区间的最大子段和。
我们的做法是，将查询的区间拆成若干个区间，然后按照pushup中的方法合并。
一个技巧是query的时候返回一个结构体，这样会比较好写。
1/* ***********************************************
2Author :111qqz
3Created Time :Fri 16 Sep 2016 03:15:50 AM CST
4File Name :code/bzoj/1756.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=5E5+7;
32int n,m;
33int a[N];
34struct Tree
35{
36 int sum;
37 int mxl;
38 int mxr;
39 int mx;
40}tree[N<<2];
41void PushUp(int rt)
42{
43 tree[rt].sum = tree[rt<<1].sum+tree[rt<<1|1].sum;
44 if (tree[rt<<1].mxr>0&&tree[rt<<1|1].mxl>0)
45 tree[rt].mx = tree[rt<<1].mxr+tree[rt<<1|1].mxl;
46 else tree[rt].mx = max(tree[rt<<1].mxr,tree[rt<<1|1].mxl);
47 tree[rt].mx = max(tree[rt].mx,max(tree[rt<<1].mx,tree[rt<<1|1].mx));
48 tree[rt].mxl=max(tree[rt<<1].mxl,tree[rt<<1].sum+tree[rt<<1|1].mxl);
49 tree[rt].mxr=max(tree[rt<<1|1].mxr,tree[rt<<1|1].sum+tree[rt<<1].mxr);
50}
51void build(int l,int r,int rt)
52{
53 // cout<<"l:"<<l<<" r:"<<r<< " rt:"<<rt<<endl;
54 if (l==r)
55 {
56 int tmp;
57 scanf("%d",&tmp);
58// cout<<"tmp:"<<tmp<<endl;
59 tree[rt].mx = tree[rt].mxl = tree[rt].mxr = tree[rt].sum = tmp;
60 return ;
61 }
62 int m = (l+r)>>1;
63 build(lson);
64 build(rson);
65 PushUp(rt);
66}
67void update( int p,int sc,int l,int r,int rt)
68{
69 if (l==r)
70 {
71 tree[rt].mx = tree[rt].mxl = tree[rt].mxr = tree[rt].sum = sc;
72 return ;
73 }
74 int m = (l+r)>>1;
75 if (p<=m) update(p,sc,lson);
76 else update(p,sc,rson);
77 PushUp(rt);
78}
79Tree query(int L,int R,int l,int r,int rt)
80{
81 if (L<=l&&r<=R) return tree[rt];
82 int m = (l+r)>>1;
83 if (L<=m&&R>=m+1)
84 {
85 Tree root,ltree,rtree;
86 ltree=query(L,R,lson);
87 rtree=query(L,R,rson);
88 root.sum = ltree.sum + rtree.sum;
89 if (ltree.mxr>0&&rtree.mxl>0)
90 root.mx = ltree.mxr + rtree.mxl;
91 else root.mx = max(ltree.mxr,rtree.mxl);
92 root.mx = max(root.mx,max(ltree.mx,rtree.mx));
93 root.mxl = max(ltree.mxl,rtree.mxl+ltree.sum);
94 root.mxr = max(rtree.mxr,ltree.mxr+rtree.sum);
95 return root;
96 }
97 else
98 if (L<=m) return query(L,R,lson);
99 else return query(L,R,rson);
100}
101int main()
102{
103 #ifndef ONLINE_JUDGE
104 freopen("code/in.txt","r",stdin);
105 #endif
106 scanf("%d%d",&n,&m);
107 build(1,n,1);
108 while (m--)
109 {
110 int opt;
111 scanf("%d",&opt);
112 if (opt==1)
113 {
114 int a,b;
115 scanf("%d%d",&a,&b);
116 if (a>b) swap(a,b);
117 int ans = query(a,b,1,n,1).mx;
118 printf("%d\n",ans);
119 }else
120 {
121 int p,x;
122 scanf("%d%d",&p,&x);
123 update(p,x,1,n,1);
124 }
125 }
126 #ifndef ONLINE_JUDGE
127 fclose(stdin);
128 #endif
129 return 0;
130}