Bzoj 1756: Vijos1083 小白逛公园线段树

1756: Vijos1083 小白逛公园　

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1021 Solved: 326
[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

HINT

Source

题解：

线段树维护。

记得查询时可能覆盖两个区间，所以要传下去结构体。

 #include<bits/stdc++.h>

 using namespace std;

 #define MAXN 500010

 struct node

 {

     int left,right,lx,rx,mx,sum;

 }tree[*MAXN];

 int a[MAXN];

 int read()

 {

     int s=,fh=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}

     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}

     return s*fh;

 }

 void Build(int k,int l,int r)

 {

     tree[k].left=l;tree[k].right=r;tree[k].sum=;

     if(l==r)return;

     int mid=(l+r)/;

     Build(k*,l,mid);Build(k*+,mid+,r);

 }

 void Pushup(int k)

 {

     tree[k].sum=tree[k*].sum+tree[k*+].sum;

     tree[k].mx=max(tree[k*].mx,tree[k*+].mx);

     tree[k].mx=max(tree[k].mx,tree[k*].rx+tree[k*+].lx);

     tree[k].lx=max(tree[k*].lx,tree[k*].sum+tree[k*+].lx);

     tree[k].rx=max(tree[k*+].rx,tree[k*+].sum+tree[k*].rx);

 }

 void Change(int k,int lr,int C)

 {

     if(tree[k].left==tree[k].right){tree[k].sum=tree[k].lx=tree[k].rx=tree[k].mx=C;return;}

     int mid=(tree[k].left+tree[k].right)/;

     if(lr<=mid)Change(k*,lr,C);

     else Change(k*+,lr,C);

     Pushup(k);

 }

 node Query_max(int k,int l,int r)

 {

     if(l<=tree[k].left&&tree[k].right<=r)return tree[k];

     int mid=(tree[k].left+tree[k].right)/;

     if(r<=mid)return Query_max(k*,l,r);

     else if(l>mid)return Query_max(k*+,l,r);

     else

     {

         node ll,rr,nn;

         ll=Query_max(k*,l,mid);rr=Query_max(k*+,mid+,r);

         nn.sum=ll.sum+rr.sum;

         nn.mx=max(ll.mx,rr.mx);

         nn.mx=max(nn.mx,ll.rx+rr.lx);

         nn.lx=max(ll.lx,ll.sum+rr.lx);

         nn.rx=max(rr.rx,rr.sum+ll.rx);

         return nn;

     }

 }

 int main()

 {

     int n,m,i,K,A,B;

     n=read();m=read();

     for(i=;i<=n;i++)a[i]=read();

     Build(,,n);

     for(i=;i<=n;i++)Change(,i,a[i]);

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

     {

         K=read();A=read();B=read();

         if(A>B&&K==)swap(A,B);

         if(K==)

         {

             node nn;

             nn=Query_max(,A,B);

             printf("%d\n",nn.mx);

         }

         else Change(,A,B);

     }

     fclose(stdin);

     fclose(stdout);

     return ;

 }

巴特西

Bzoj 1756: Vijos1083 小白逛公园线段树

1756: Vijos1083 小白逛公园

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

巴特西

Bzoj 1756: Vijos1083 小白逛公园 线段树

1756: Vijos1083 小白逛公园

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

Bzoj 1756: Vijos1083 小白逛公园线段树

1756: Vijos1083 小白逛公园　