61.187.179.132:8080/JudgeOnline/showproblem

Vijos1083 小白逛公园　

Time Limit:10000MS  Memory Limit:65536K
Total Submit:58 Accepted:16
Case Time Limit:1000MS

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

Source

这是一道水题啊水题啊。我实验了一下我最近想出来的线段树新写法。就是合并用一个失效值来代替不存在的节点。。然后不是在父节点处判断范围，而是直接在子节点处判断范围，写起来超爽，代码也超短，具体看Code吧。
Code：
#include<cstdio>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int inf=~0U>>1,maxn=500000;
int A[maxn];
struct info
{
int L,R,M,S;
info(int x=0):L(x),R(x),M(x),S(x){}
}none;
info operator+(const info&l,const info&r)
{
info f;if(l.M==-inf)return r;
if(r.M==-inf)return l;
f.L=max(l.L,l.S+r.L);
f.R=max(r.R,r.S+l.R);
f.S=l.S+r.S;
f.M=max(l.M,r.M);
f.M=max(f.M,l.R+r.L);
return f;
}
info T[maxn*3];
inline void set(int t,int x)
{
T[t]=info(x);
}
void build(int t,int l,int r)
{
if(l+1==r) {set(t,A[l]);return;}
build(t*2,l,(l+r)/2);
build(t*2+1,(l+r)/2,r);
T[t]=T[t*2]+T[t*2+1];
}
void change(int t,int l,int r,int p,int s)
{
if(l+1==r){set(t,s);return;}
if(p<(l+r)/2) change(t*2,l,(l+r)/2,p,s);
else change(t*2+1,(l+r)/2,r,p,s);
T[t]=T[t*2]+T[t*2+1];
}
info ask(int t,int l,int r,int a,int b)
{
if(b<=l||a>=r) return none;
if(l>=a&&r<=b) return T[t];
return ask(t*2,l,(l+r)/2,a,b)+ask(t*2+1,(l+r)/2,r,a,b);
}
int main()
{
//freopen("in","r",stdin);
none.M=-inf;
int n,m,a,b,c;scanf("%d %d",&n,&m);
rep(i,n)scanf("%d",A+i);
build(1,0,n);
while(m–)
{
scanf("%d %d %d",&a,&b,&c);
if(a==1) {if(b>c)swap(b,c);printf("%dn",ask(1,0,n,b-1,c).M);}
else change(1,0,n,b-1,c);
}
}