G - 程序设计竞赛
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
“你动规无力，图论不稳，数据结构松散，贪心迟钝，没一样像样的，就你还想和我同台竞技，做你的美梦！今天这场比赛，就是要让你知道你是多么的无能！！”
不训练，无以为战。有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 4 1 2 3 4 0 1 3 1 3 -3 0 2 4 0 3 3 |
6 4 -3 |
题意大概是，给定一个序列，要求序列支持修改时间<=o(lgn),区间查询连续序列之和最大值时间<=o(lgn).
要用线段树，记录好多东东。。。。
我是加了4个记录
struct mm{
int left;
int right;
int l;
int r;
int data;
int sum;
}tree[400005]={};
Left,right 是区间范围，
.l是存当前区间从右开始最大的连续序列之和。
.r是存当前区间从左开始最大的连续序列之和。
.data 是存当前区间的最大的连续序列之和。
.sum是存当前区间的所有元素之和。
然后修改序列时就有
int g=l*2,h=l*2+1;
tree[l].l=max(tree[g].sum+tree[h].l,tree[g].l);
tree[l].r=max(tree[h].sum+tree[g].r,tree[h].r);
tree[l].sum=tree[g].sum+tree[h].sum;
tree[l].data=max(tree[g].r+tree[h].l,max(tree[g].data,tree[h].data));
从左开始最大的连续序列之和可以是
这两种情况，即max(tree[g].sum+tree[h].l,tree[g].l);
黑色表示该区间的最大的连续序列之和
从右开始同理。
而data就是
这三种情况
即max(tree[g].r+tree[h].l,max(tree[g].data,tree[h].data));
然后查找区间，suan是计算在L区间内从j到k的最大的连续序列之和，先要找到包含[j,k]的最小区间[L.left,L.right],然后就和上图一样了。
int suan(int l,int j,int k)
{
if (tree[l].left==j && tree[l].right==k) return tree[l].data;
if ((tree[l].left+tree[l].right)/2<j) return suan(l*2+1,j,k);
if ((tree[l].left+tree[l].right)/2>=k) return suan(l*2,j,k);
int g,h;
g=suanr(l*2,j);
h=suanl(l*2+1,k);
int a,s;
a=suan(l*2,j,(tree[l].left+tree[l].right)/2);
s=suan(l*2+1,(tree[l].left+tree[l].right)/2+1,k);
return max(g+h,max(a,s));
}
其中suanr和suanl是计算L区间从右或从左最大的连续序列之和。
int suanr(int l,int j)
{
if (tree[l].left==j) return tree[l].r;
if ((tree[l].right+tree[l].left)/2+1<=j) return suanr(l*2+1,j);
return max(tree[l*2+1].r,tree[l*2+1].sum+suanr(l*2,j));
}
int suanl(int l,int j)
{
if (tree[l].right==j) return tree[l].l;
if ((tree[l].right+tree[l].left)/2>=j) return suanl(l*2,j);
return max(tree[l*2].l,tree[l*2].sum+suanl(l*2+1,j));
}
#include <iostream> #include<cstdio> using namespace std; int M; struct mm{ int left; int right; int l; int r; int data; int sum; }tree[400005]={}; void build(int l,int j,int k) { tree[l].left=j; tree[l].right=k; if (j==k) return; build(l*2,j,(j+k)/2); build(l*2+1,(j+k)/2+1,k); } void cha(int l,int j,int light) { if (tree[l].right==tree[l].left) { tree[l].l=tree[l].r=tree[l].sum=tree[l].data=light; return; } if ((tree[l].right+tree[l].left)/2<j) cha(l*2+1,j,light); else cha(l*2,j,light); int g=l*2,h=l*2+1; tree[l].l=max(tree[g].sum+tree[h].l,tree[g].l); tree[l].r=max(tree[h].sum+tree[g].r,tree[h].r); tree[l].sum=tree[g].sum+tree[h].sum; tree[l].data=max(tree[g].r+tree[h].l,max(tree[g].data,tree[h].data)); } int suanr(int l,int j) { if (tree[l].left==j) return tree[l].r; if ((tree[l].right+tree[l].left)/2+1<=j) return suanr(l*2+1,j); return max(tree[l*2+1].r,tree[l*2+1].sum+suanr(l*2,j)); } int suanl(int l,int j) { if (tree[l].right==j) return tree[l].l; if ((tree[l].right+tree[l].left)/2>=j) return suanl(l*2,j); return max(tree[l*2].l,tree[l*2].sum+suanl(l*2+1,j)); } int suan(int l,int j,int k) { if (tree[l].left==j && tree[l].right==k) return tree[l].data; if ((tree[l].left+tree[l].right)/2<j) return suan(l*2+1,j,k); if ((tree[l].left+tree[l].right)/2>=k) return suan(l*2,j,k); int g,h; g=suanr(l*2,j); h=suanl(l*2+1,k); int a,s; a=suan(l*2,j,(tree[l].left+tree[l].right)/2); s=suan(l*2+1,(tree[l].left+tree[l].right)/2+1,k); return max(g+h,max(a,s)); } int main() { int g,h,j,k,l,n; cin>>n>>M; build(1,1,n); for (j=1;j<=n;j++){ scanf("%d",&g); cha(1,j,g); } for (j=1;j<=M;j++){ scanf("%d%d%d",&g,&h,&k); if (g==1) cha(1,h,k); else { printf("%d ",suan(1,h,k)); } } return 0; }