vijos1083：小白逛公园

描述

小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着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

样例输出1

2
-1

限制

各个测试点2s

分析

求最大子段和，线段树维护四个值，区间和，区间最大子段和，区间从左边开始的最大子段和，从右边开始的最大子段和。

最大值从左区间，右区间，中间取最大的

时限2S。

code

  1 #include<cstdio>
  2 #include<algorithm>
  3 #define lson l,m,rt<<1
  4 #define rson m+1,r,rt<<1|1
  5 
  6 using namespace std;
  7 const int MAXN = 2000100;
  8 
  9 int mx[MAXN],sum[MAXN],lm[MAXN],rm[MAXN];
 10 int n,q;
 11 
 12 void pushup(int rt)
 13 {
 14     sum[rt] = sum[rt<<1]+sum[rt<<1|1];
 15     lm[rt] = max(sum[rt<<1]+lm[rt<<1|1],lm[rt<<1]);
 16     rm[rt] = max(sum[rt<<1|1]+rm[rt<<1],rm[rt<<1|1]);
 17     mx[rt] = max(max(mx[rt<<1],mx[rt<<1|1]),rm[rt<<1]+lm[rt<<1|1]);
 18 }
 19 void update(int l,int r,int rt,int x,int v)
 20 {
 21     if (l==r)
 22     {
 23         sum[rt] = mx[rt] = lm[rt] = rm[rt] = v;
 24         return ;
 25     }
 26     
 27     int m = (l+r)>>1;
 28     if (x<=m) update(lson,x,v);
 29     else update(rson,x,v);
 30     pushup(rt);
 31 }
 32 void build(int l,int r,int rt)
 33 {
 34     if (l==r)
 35     {
 36         scanf("%d",&sum[rt]);
 37         mx[rt] = lm[rt] = rm[rt] = sum[rt];
 38         return ;
 39     }
 40     int m = (l+r)>>1;
 41     build(lson);
 42     build(rson);
 43     pushup(rt);
 44 }
 45 int query_l(int l,int r,int rt,int L,int R)
 46 {
 47     if (l==L&&r==R) return rm[rt];
 48     int m = (l+r)>>1;
 49     if (L>m) return query_l(rson,L,R);
 50     else
 51     {
 52         int t1 = rm[rt<<1|1];
 53         int t2 = sum[rt<<1|1]+query_l(lson,L,m);
 54         return max(t1,t2);
 55     }
 56 }
 57 int query_r(int l,int r,int rt,int L,int R)
 58 {
 59     if (l==L&&r==R) return lm[rt];
 60     int m = (l+r)>>1;
 61     if (R<=m) return query_r(lson,L,R);
 62     else
 63     {
 64         int t1 = lm[rt<<1];
 65         int t2 = sum[rt<<1]+query_r(rson,m+1,R);
 66         return max(t1,t2);
 67     }
 68 }
 69 int query(int l,int r,int rt,int L,int R)
 70 {
 71     if (L<=l&&r<=R) return mx[rt];
 72     if (L>r||l>R) return 0;
 73     int m = (l+r)>>1;
 74     int ret = 0,max_l = 0,max_r = 0,tl = 0,tr = 0;
 75     if (L>m) return query(rson,L,R);
 76     else if (R<=m) return query(lson,L,R);
 77     else
 78     {
 79         tl = query(lson,L,m);
 80         tr = query(rson,m+1,R);
 81         max_l = query_l(lson,L,m);
 82         max_r = query_r(rson,m+1,R);
 83         return max(max(tl,tr),max_l+max_r);
 84     }
 85 }
 86 int main()
 87 {
 88     scanf("%d%d",&n,&q);
 89     build(1,n,1);
 90     int opt,x,y;
 91     while (q--)
 92     {
 93         scanf("%d%d%d",&opt,&x,&y);
 94         if (opt==1)
 95         {
 96             if (x>y) swap(x,y);
 97             printf("%d
",query(1,n,1,x,y));    
 98         }
 99         else update(1,n,1,x,y);
100     }
101     return 0;
102 }