程序设计竞赛
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
“你动规无力，图论不稳，数据结构松散，贪心迟钝，没一样像样的，就你还想和我同台竞技，做你的美梦！今天这场比赛，就是要让你知道你是多么的无能！！”
不训练，无以为战。有n项能力是ACM竞赛要求的，训练则能提升，忽略则会荒废。
这m天，你能做到如何。
Input
第一行两个整数n，m,分别表示有n项能力要求，共有m天。
第二行n个整数，第i个整数ai表示第i项能力的数值。
接下来m行，每行开始先读入一个整数si，表明这是一次询问还是一次能力变化。
si=0，表明这是一次询问，然后读入两个整数li,ri，表示询问在[li，ri]区间中任选一段连续序列，这段序列中所有能力值之和最大能是多少。
si=1，表明这是一次能力变化，然后读入两个整数xi,wi，表示第xi项能力变为了wi。
1≤n,m≤100000,−10000≤ai≤10000,1≤li≤ri≤n,1≤xi≤n,−10000≤wi≤10000
Output
有多少询问就输出多少行，每行输出一个整数，作为对该询问的回答。
Sample input and output
| Sample Input | Sample Output |
|---|---|
4 41 2 3 40 1 31 3 -30 2 40 3 3 | 64-3 |
思路：
每个节点维护4个值：
summ:此区间内的最大连续和sum_:该节点以下的节点值得总和suml:此区间的从左端开始的最大连续和sumr:此区间的从右端开始的最大连续和合并区间时，该区间的最大连续和为：max(左子节点的最大连续和，右子节点的最大连续和，左子节点的最大右连续和+右子节点的最大左连续和)查询时返回一个整节点。因为每次要查询左子节点和右子节点，并且要比较它们的右连续最大和和左连续最大和，所以需要返回整个节点以便求值。
代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 #define INF 0x7fffffff 10 const int N=100005; 11 int n,m,a[N]; 12 struct node 13 { 14 int left,right; 15 int sum_,summ,suml,sumr; 16 }tree[4*N]; 17 18 void build(int id,int l,int r);//建一棵线段树 19 node query_sum(int id,int l,int r);//查询区间和 20 void update(int id,int pos,int val);//更新位置pos的值 21 22 int main() 23 { 24 //freopen("D:\\input.in","r",stdin); 25 //freopen("D:\\output.out","w",stdout); 26 int bo,t1,t2; 27 scanf("%d%d",&n,&m); 28 for(int i=1;i<=n;i++) 29 scanf("%d",&a[i]); 30 build(1,1,n); 31 for(int i=1;i<=m;i++) 32 { 33 scanf("%d%d%d",&bo,&t1,&t2); 34 if(bo) 35 update(1,t1,t2); 36 else{ 37 node tmp=query_sum(1,t1,t2); 38 printf("%d\n",tmp.summ); 39 } 40 } 41 return 0; 42 } 43 void build(int id,int l,int r) 44 { 45 tree[id].left=l; 46 tree[id].right=r; 47 if(l==r) 48 { 49 tree[id].sum_=a[l]; 50 tree[id].summ=a[l]; 51 tree[id].suml=a[l]; 52 tree[id].sumr=a[l]; 53 } 54 else 55 { 56 int mid=(l+r)/2; 57 build(2*id,l,mid); 58 build(2*id+1,mid+1,r); 59 tree[id].sum_=tree[2*id].sum_+tree[2*id+1].sum_; 60 tree[id].summ=max(max(tree[2*id].summ,tree[2*id+1].summ),(tree[2*id].sumr+tree[2*id+1].suml)); 61 tree[id].suml=max(tree[2*id].suml,tree[2*id].sum_+tree[2*id+1].suml); 62 tree[id].sumr=max(tree[2*id+1].sumr,tree[2*id].sumr+tree[2*id+1].sum_); 63 } 64 } 65 node query_sum(int id,int l,int r) 66 { 67 if(tree[id].left==l&&tree[id].right==r) 68 return tree[id]; 69 else 70 { 71 node tmp,k1,k2; 72 int flag1=0,flag2=0; 73 int mid=(tree[id].left+tree[id].right)/2; 74 if(r<=mid) return query_sum(2*id,l,r); 75 if(l>mid) return query_sum(2*id+1,l,r); 76 if(l<=mid){ 77 k1=query_sum(2*id,l,mid); 78 flag1=1; 79 } 80 if(r>mid){ 81 k2=query_sum(2*id+1,mid+1,r); 82 flag2=1; 83 } 84 if(flag1&flag2){ 85 tmp.sum_=k1.sum_+k2.sum_; 86 tmp.suml=max(k1.suml,k1.sum_+k2.suml); 87 tmp.sumr=max(k2.sumr,k1.sumr+k2.sum_); 88 tmp.summ=max(max(k1.summ,k2.summ),k1.sumr+k2.suml); 89 }else{ 90 if(flag1) tmp=k1; 91 else tmp=k2; 92 } 93 return tmp; 94 } 95 } 96 void update(int id,int pos,int val) 97 { 98 if(tree[id].left==tree[id].right) 99 {100 tree[id].sum_=val;101 tree[id].summ=val;102 tree[id].suml=val;103 tree[id].sumr=val;104 }105 else106 {107 int mid=(tree[id].left+tree[id].right)/2;108 if(pos<=mid) update(2*id,pos,val);109 else update(2*id+1,pos,val);110 tree[id].sum_=tree[2*id].sum_+tree[2*id+1].sum_;111 tree[id].summ=max(max(tree[2*id].summ,tree[2*id+1].summ),(tree[2*id].sumr+tree[2*id+1].suml));112 tree[id].suml=max(tree[2*id].suml,tree[2*id].sum_+tree[2*id+1].suml);113 tree[id].sumr=max(tree[2*id+1].sumr,tree[2*id].sumr+tree[2*id+1].sum_);114 }115 }