Vijos 1083 小白逛公园(线段树)

Vijos 1083 小白逛公园(线段树)

线段树,每个结点维护区间内的最大值M,和sum,最大前缀和lm,最大后缀和rm.

若要求区间为[a,b],则答案max(此区间M,左儿子M,右儿子M,左儿子rm+右儿子lm).

---------------------------------------------------------------------------------

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define rep(i,n) for(int i=0;i<n;++i)
#define clr(x,c) memset(x,c,sizeof(x))
#define Rep(i,l,r) for(int i=1;i<=r;++i)
#define mid(a,b) ((a+b)>>1)
#define lc(x) (x<<1)
#define rc(x) (lc(x)+1)
 
using namespace std;
 
const int maxn=500000+10,maxnode=maxn*4;
const int inf=0x7fffffff;
 
int a[maxn];
 
struct Segment_Tree {
    
    struct node {
    int l,r;
    int lm,rm,M,sum;
    node operator + (const node &x) {
       node o;
         o.lm=max(lm,sum+x.lm);
       o.rm=max(x.rm,x.sum+rm);
       o.sum=sum+x.sum;
       o.M=max(max(M,x.M),rm+x.lm);
       return o;
    }
    };
   
    node st[maxnode];
     
    inline int update(int x) {
  node &o=st[x],&L=st[lc(x)],&R=st[rc(x)];
    o.lm=max(L.lm,L.sum+R.lm);
    o.rm=max(R.rm,R.sum+L.rm);
    o.sum=L.sum+R.sum;
    o.M=max(max(L.M,R.M),L.rm+R.lm);
}
     
    void Build(int x,int l,int r) {
    node &o=st[x];
    o.l=l; o.r=r;
    int m=mid(l,r);
    if(l==r) o.lm=o.rm=o.M=o.sum=a[l];
    else {
    if(l<=m) Build(lc(x),l,m);
    if(m<r) Build(rc(x),m+1,r);
    update(x);
    }
    }
     
    int p,v;
    void Update(int x) {
    node &o=st[x];
    int l=o.l,r=o.r;
    if(l==r) o.sum=o.lm=o.rm=o.M=v;
    else {
    int m=mid(l,r);
    if(p<=m) Update(lc(x));
    if(m<p) Update(rc(x));
    update(x);
    }
    }
    inline void UPDATE(int p,int v) {
    this->p=p; this->v=v;
    Update(1);
    }
     
    int ql,qr;
    node query(int x) {
    node &o=st[x];
    int l=o.l,r=o.r;
    if(ql<=l && r<=qr) return st[x];
    int m=mid(l,r);
    if(qr<=m) return query(lc(x));
    if(ql>m) return query(rc(x));
    return query(lc(x))+query(rc(x));
    }  
     
    inline int Query(int l,int r) {
    ql=l; qr=r;
    return query(1).M;
    }
} ST;
     
int main()
{
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
Rep(i,1,n) scanf("%d",&a[i]);
ST.Build(1,1,n);
while(m--) {
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(x==1) printf("%d\n",ST.Query(min(y,z),max(y,z)));
else ST.UPDATE(y,z);
}
return 0;
}

---------------------------------------------------------------------------------

描述

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

上一篇:《Python数据分析》环境搭建之安装Jupyter工具(一)


下一篇:malloc与new的区别