描述

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

Copy

样例输出1

2

-1

Copy

限制

各个测试点2s

这是一道线段树的题，和一般不同的是这道题求一个区间内连续几个的最大值，这个就要多定义一个从左边开始和从右边开始的连续最大值lmax和rmax

在简单的提醒后，很快的把题的大部分打完了，最后卡在询问环节，还是多亏了大佬Ztraveler的帮助点醒了我

我就简单的提一下我卡住的地方

当我们要求出的L和R区间的LR在mid的同一侧就是一个简单的询问操作，但是当L和R分居mid的两侧时，就要稍作处理

我和那位大佬的方法是新开三个结构体，ly，ry，yy，分别是L到mid，mid+1到R和L到R，这样下来就可以就出L到R中的答案了

然后再提醒一点小细节，就是查询时a可能大于b也可能小于b

说的可能不是很清晰，还是看代码分析吧

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #include<cstdlib>

 #define maxn 500005

 #define lson pos<<1

 #define rson pos<<1|1

 using namespace std;

 struct node{

     int sum,l,r,lmax,rmax,maxx;

 }e[maxn*];

 int a[maxn],n,m;

 void pushup(int pos)//更新操作

 {

         e[pos].sum=e[lson].sum+e[rson].sum;

         e[pos].lmax=max(e[lson].lmax,e[lson].sum+e[rson].lmax);

         e[pos].rmax=max(e[rson].rmax,e[rson].sum+e[lson].rmax);

         e[pos].maxx=max(max(max(e[lson].lmax,e[rson].rmax),e[lson].rmax+e[rson].lmax),max(e[lson].maxx,e[rson].maxx));

 }

 void build(int l,int r,int pos)

 {

     e[pos].l=l;e[pos].r=r;

     if(l==r)

     {

         e[pos].lmax=a[l];

         e[pos].rmax=a[l];

         e[pos].maxx=a[l];

         e[pos].sum =a[l];

     }else{

         int mid=(l+r)>>;

         build(l,mid,lson);

         build(mid+,r,rson);

         pushup(pos);

     }

 }    

 node  query(int l,int r,int pos)

 {

     if(e[pos].l==l&&e[pos].r==r)

     {

         return e[pos];

     }else{

         int mid=(e[pos].l+e[pos].r)>>;

         if(mid>=r){

             return query(l,r,pos<<);

         }else{

             if(mid<l)return query(l,r,pos<<|);

             else {//当要找的LR分居mid两侧

                 node ly=query(l,mid,lson);

                 node ry=query(mid+,r,rson);

                 node yy;

                 yy.sum=ly.sum+ry.sum;

                 yy.lmax=max(ly.lmax,ly.sum+ry.lmax);

                 yy.rmax=max(ry.rmax,ry.sum+ly.rmax);

                 yy.maxx=max(max(max(ly.lmax,ry.rmax),ly.rmax+ry.lmax),max(ly.maxx,ry.maxx));

                 return yy;

             }

         }

     }

 }

 void change(int l,int r,int k,int x,int pos)

 {

     if(l==k&&r==k)

     {

         e[pos].lmax=e[pos].rmax=e[pos].maxx=e[pos].sum=x;

     }else{

         int mid=(l+r)>>;

         if(k<=mid)

         {

             change(l,mid,k,x,pos<<);

             pushup(pos);

         }else{

             change(mid+,r,k,x,pos<<|);

             pushup(pos);

         }

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)

     {

         scanf("%d",&a[i]);

     }

     build(,n,);

     for(int i=;i<=m;i++)

     {

         int q;

         scanf("%d",&q);

         if(q==)

         {

             int a,b;

             scanf("%d%d",&a,&b);

             if(a>b)printf("%d\n",query(b,a,).maxx);

             else printf("%d\n",query(a,b,).maxx);//不要被这个小细节坑了

         }else{

             int a,b;

             scanf("%d%d",&a,&b);

             change(,n,a,b,);

         }

     }

 }

做完这题整个人都不好了，感觉这点细节都看不到，我的oi之路艰难啊！！！

ps：代码写的比较稀疏，看起来很多，其实不难的

巴特西

[vijos]1083小白逛公园<线段树>

描述

格式

输入格式

输出格式

样例1

样例输入1

样例输出1

限制

最新文章

热门文章