题意翻译
nn 个数，qq 次操作
操作0 x y把A_xAx 修改为yy
操作1 l r询问区间[l, r][l,r] 的最大子段和
感谢 @Edgration 提供的翻译
题目描述
You are given a sequence A of N (N <= 50000) integers between -10000 and 10000. On this sequence you have to apply M (M <= 50000) operations:
modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.输入输出格式
输入格式：
The first line of input contains an integer N. The following line contains N integers, representing the sequence A1..AN.
The third line contains an integer M. The next M lines contain the operations in following form:0 x y: modify Ax into y (|y|<=10000).1 x y: print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.
输出格式：
For each query, print an integer as the problem required.
输入输出样例
输入样例#1：
41 2 3 441 1 30 3 -31 2 41 3 3
输出样例#1：
64-3 其实很基础的一道线段树，但是赛场上就是调不通，又是一次赛后AC的典范，一定是我写代码的方式不对。。。
1 #include2 #define mid ((t[d].l + t[d].r) >> 1) 3 using namespace std; 4 const int N = 50005; 5 struct Tree{ 6 int l,r,lgss,rgss,gss,sum; 7 }t[N*8]; 8 9 int n,m;10 int a[N];11 12 void build(int d,int l,int r){13 t[d].l = l;t[d].r = r;14 if (l == r){15 t[d].gss = t[d].lgss = t[d].rgss = t[d].sum = a[l];16 return;17 }18 build(d*2,l,mid);19 build(d*2+1,mid+1,r);20 t[d].sum = t[d*2].sum + t[d*2+1].sum;21 t[d].gss = max(t[d*2].gss,max(t[d*2+1].gss,t[d*2].rgss+t[d*2+1].lgss));22 t[d].lgss = max(t[d*2].lgss,t[d*2].sum + t[d*2+1].lgss);23 t[d].rgss = max(t[d*2+1].rgss,t[d*2].rgss + t[d*2+1].sum);24 }25 26 void modify(int d,int x,int y){27 if (t[d].l == x && t[d].r == x){28 t[d].gss = t[d].lgss = t[d].rgss = t[d].sum = y;29 return;30 }31 if (x <= mid) modify(d*2,x,y);32 else if (x > mid) modify(d*2+1,x,y);33 t[d].sum = t[d*2].sum + t[d*2+1].sum;34 t[d].gss = max(t[d*2].gss,max(t[d*2+1].gss,t[d*2].rgss+t[d*2+1].lgss));35 t[d].lgss = max(t[d*2].lgss,t[d*2].sum + t[d*2+1].lgss);36 t[d].rgss = max(t[d*2+1].rgss,t[d*2].rgss + t[d*2+1].sum);37 }38 39 int getl(int d,int l,int r){40 if (t[d].l == l && t[d].r == r){41 return t[d].lgss;42 }43 if (r > mid){44 return max(getl(d*2,l,mid),t[d*2].sum + getl(d*2+1,mid+1,r));45 }46 return getl(d*2,l,r);47 }48 49 int getr(int d,int l,int r){50 if (t[d].l == l && t[d].r == r){51 return t[d].rgss;52 }53 if (l <= mid){54 return max(getr(d*2+1,mid+1,r),getr(d*2,l,mid) + t[d*2+1].sum);55 }else return getr(d*2+1,l,r);56 }57 58 int get(int d,int l,int r){59 if (t[d].l == l && t[d].r == r){60 return t[d].gss;61 }62 if (r <= mid) return get(d*2,l,r);63 else if (l > mid) return get(d*2+1,l,r);64 return max(get(d*2,l,mid),max(get(d*2+1,mid+1,r),getr(d*2,l,mid)+getl(d*2+1,mid+1,r)));65 }66 67 int main(){68 scanf("%d",&n);69 for (int i = 1;i <= n;++i){70 scanf("%d",a+i);71 72 }73 build(1,1,n);74 scanf("%d",&m);75 for (int i = 0;i < m;++i){76 int kk,x,y;77 scanf("%d%d%d",&kk,&x,&y);78 if (kk == 0){79 modify(1,x,y);80 }else {81 printf("%d\n",get(1,x,y));82 }83 }84 }