题目描述
小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。
一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。
那么，就请你来帮小白选择公园吧。
输入格式
第一行，两个整数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的整数。
输出格式
小白每出去玩一次，都对应输出一行，只包含一个整数，表示小白可以选出的公园得分和的最大值。
样例输入
5 3
1
2
-3
4
5
1 2 3
2 2 -1
1 2 3
样例输出
2
-1
评测链接：rqnoj：http://www.rqnoj.cn/Problem_626.html
vijos：https://vijos.org/p/1083
(vijos上数据比较弱，用来检验一下你写对没就行了，最好是能够交到rqnoj上通过了，才说明你写的算是过关了。)
解法：
这是鄙人第一次写的比较高级的线段树，用了包括内敛函数、手写读入输出优化等各种优化，交了n遍总算通过了。
我交到rqnoj上一共是耗费了4813ms，第一的大牛是2281ms，水平不够，不晓得是哪么做的，有大牛知道点拨一下，万分感激。
好了，接下来说我自己的解题思路：
1.用d[p].l记录区间p从用左端开始的最大连续区间字段和，d[p].r记录区间p从用右端开始的最大连续区间字段和，d[p].s记录区间p的总和，d[p].s记录区间p的最大连续子区间和。
2.手写读入输出，内敛函数。
3.用dd[i]记录[i,i]在线段树中的位置，用build_init()直接读入最开始的一棵树，当l==r时就读入，dd[l]就赋值为此时的节点编号。
4.用f[j]记录线段树中节点j的子树是否有变化，每次重建树时，只对子树有变化的节点进行重建。
5.用q[maxn]记录一段连续的操作2中，被改变的节点编号，直到遇到第一个操作1时，就先对q队列中的节点的所有父亲结点的f值标记为1，然后进行树的重建。
有一些详细的代码细节就不再赘述，可以看我的代码（按上面的分点来看，应该能看懂）。
代码：
#include<Cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#define maxn (500000+100)
using namespace std;
struct tnode{int l,r,s,m;}d[maxn*3];
int dd[maxn],q[maxn];
bool f[maxn*3];
void init()
{
freopen("rq626.in","r",stdin);
freopen("rq626_4.out","w",stdout);
}
//手写读入输出
inline int getin()
{
int ans=0;bool sign=0;char tmp;
do tmp=getchar();
while(!isdigit(tmp)&&tmp!='-');
if(tmp=='-')tmp=getchar(),sign=1;
do ans=(ans<<3)+(ans<<1)+tmp-'0';
while(isdigit(tmp=getchar()));
return sign?-ans:ans;
}
//得到区间a，b的父亲结点的各项值
inline tnode data(tnode a,tnode b)
{
tnode k;
k.l=max(a.l,a.s+b.l);
k.r=max(b.r,b.s+a.r);
k.m=max(max(a.m,b.m),a.r+b.l);
k.s=a.s+b.s;
return k;
}
//读入原始的第一棵树
void build_init(int p,int l,int r)
{
if(l==r)
{
int x=getin();dd[l]=p;
d[p].l=d[p].r=d[p].m=d[p].s=x;
return;
}
int m=(l+r)>>1,k=p<<1;
build_init(k,l,m),build_init(k+1,m+1,r);
d[p]=data(d[k],d[k+1]);
}
//对子节点有变化的点进行染色
inline void ranse(int i)
{
int k=i>>1;
while(k>1 && !f[k])
f[k]=1,k=k>>1;
}
//对子节点有变化的树进行重建
void build(int p,int l,int r)
{
int m=(l+r)>>1,k=p<<1;
if(f[k])build(k,l,m),f[k]=0;
if(f[k+1])build(k+1,m+1,r),f[k+1]=0;
d[p]=data(d[k],d[k+1]);
}
tnode get(int p,int pl,int pr,int l,int r)
{
if(l<=pl && pr<=r)return d[p];
int m=(pl+pr)>>1,k=p<<1;
if(r<=m) return get(k,pl,m,l,r);//[l,r]只在p的左子树
if(l>m) return get(k+1,m+1,pr,l,r);//[l,r]只在p的右子树
tnode t1=get(k,pl,m,l,r);//跨区间
tnode t2=get(k+1,m+1,pr,l,r);
return data(t1,t2);
}
void work()
{
int n=getin(),m=getin();
build_init(1,1,n); int i;
for(i=1;i<=n;i++)ranse(dd[i]);
//q2记录上一个操作是否是2
//q[maxn]记录连续的一段操作2所改变的节点，遇到第一个操作1时就对子节点有
//变化的点进行重建。
bool q2=0; int l,r=0,kk,k,a,b;
for(i=1;i<=m;i++)
{
k=getin();a=getin();b=getin();
if(k==2)
{
kk=dd[a],q2=1; q[++r]=kk;
d[kk].l=d[kk].r=d[kk].m=d[kk].s=b;
}
else
{
if(a>b)swap(a,b); l=1;
while(l<=r)ranse(q[l++]);
r=0;
if(n>1 && q2)build(1,1,n);//判断n>1,若n=1就不必建树了；
q2=0; //q2=1，代表这是一段连续操作2后的第一个操作1
printf("%d\n",get(1,1,n,a,b).m);
}
}
}
int main()
{
init();
work();
return 0;
}