总是在卡。。。无语
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 500010

using namespace std;

struct Treenode
{
int left_max,right_max,all_max,sum;
}tree[MAXN<<2];

inline void update(int);
void modify(int,int,int,int,int);
Treenode query(int,int,int,int,int);

int main()
{
freopen("in.txt","r",stdin);
memset(tree,0,sizeof(tree));
int N,M;
scanf("%d%d",&N,&M);
for(int i=1,X;i<=N;i++)
{
scanf("%d",&X);
modify(1,1,N,i,X);
}
for(int i=0,K,A,B;i<M;i++)
{
scanf("%d%d%d",&K,&A,&B);
if (K==1)
{
if (A>B) swap(A,B);
printf("%d\n",query(1,1,N,A,B).all_max);
}
else modify(1,1,N,A,B);
}
return 0;
}

void modify(int pos,int l,int r,int aim,int value)
{
if (l==r&&r==aim)
{
tree[pos].left_max=tree[pos].right_max=tree[pos].all_max=tree[pos].sum=value;
return;
}
int mid=(l+r)>>1;
if (aim<=mid) modify(pos<<1,l,mid,aim,value);
if (mid<aim) modify((pos<<1)+1,mid+1,r,aim,value);
update(pos);
}

Treenode query(int pos,int l,int r,int ll,int rr)
{
if (ll<=l&&r<=rr) return tree[pos];
int mid=(l+r)>>1;
if (rr<=mid) return query(pos<<1,l,mid,ll,rr);
else if (mid<ll) return query((pos<<1)+1,mid+1,r,ll,rr);
else
{
Treenode res,res1=query(pos<<1,l,mid,ll,rr),res2=query((pos<<1)+1,mid+1,r,ll,rr);
res.sum=res1.sum+res2.sum;
res.left_max=max(res1.left_max,res1.sum+res2.left_max);
res.right_max=max(res2.right_max,res2.sum+res1.right_max);
res.all_max=max(res1.right_max+res2.left_max,max(res1.all_max,res2.all_max));
return res;
}
}

inline void update(int pos)
{
tree[pos].sum=tree[pos<<1].sum+tree[(pos<<1)+1].sum;
tree[pos].left_max=max(tree[pos<<1].left_max,tree[pos<<1].sum+tree[(pos<<1)+1].left_max);
tree[pos].right_max=max(tree[(pos<<1)+1].right_max,tree[(pos<<1)+1].sum+tree[pos<<1].right_max);
tree[pos].all_max=max(tree[pos<<1].right_max+tree[(pos<<1)+1].left_max,max(tree[pos<<1].all_max,tree[(pos<<1)+1].all_max));
}

线段树的各种sum操作，不用lazy省了不少力。不过用了我接近两个小时的时间才搞出来囧...连吃饭都在想...
维护left_sum,right_sum,sum,max_sum四种和情况。询问的时候细心就可以过了。

maintain:
p[x].sum = p[p[x].s[0]].sum + p[p[x].s[1]].sum;
p[x].left_sum = max{ p[p[x].s[0]].sum + p[p[x].s[1]].left_sum,p[p[x].s[0]].left_sum };
p[x].right_sum = max{ p[p[x].s[1]].sum+p[p[x].s[0]].right_sum,p[p[x].s[1]].right_sum };
p[x].max_sum = max{ p[p[x].s[0]].max_sum , p[p[x].s[1]].max_sum ，p[p[x].s[0]].right_sum + p[p[x].s[1]].left_sum };

看到那些1A的大神果断跪了,我调了好长时间啊
感觉写的好难看,开了不需要的东西
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define LEFT_SON (pos<<1)
#define RIGHT_SON ((pos<<1)+1)
#define MAX 500010
using namespace std;

struct ComplexTree{
int max_l,max_r;
int max_all;
int sum;
}tree[MAX*4];
struct Complex{
int max_left,max_right;
int max_,sum;
};

int source[MAX];
int total,step;

void BuildTree(int l,int r,int pos);
Complex Ask(int ask_l,int ask_r,int l,int r,int pos);
void Modify(int aim,int l,int r,int pos,int num);

int main()
{
cin>>total>>step;
for(int i=1;i<=total;i++)
scanf("%d",&source[i]);
BuildTree(1,total,1);
for(int flag,i=1;i<=step;i++)
{
scanf("%d",&flag);
if(flag==1){
int x,y;
scanf("%d%d",&x,&y);
if(x>y) swap(x,y);
printf("%d\n",Ask(x,y,1,total,1).max_);
}
else{
int pos,num;
scanf("%d%d",&pos,&num);
Modify(pos,1,total,1,num);
}
}
return 0;
}

void BuildTree(int l,int r,int pos)
{
if(l==r){
tree[pos].max_l=tree[pos].max_r=source[l];
tree[pos].sum=tree[pos].max_all=source[l];
return ;
}
int mid=(l+r)>>1;
BuildTree(l,mid,pos<<1);
BuildTree(mid+1,r,(pos<<1)+1);
tree[pos].max_l=max(tree[LEFT_SON].max_l,tree[RIGHT_SON].max_l+tree[LEFT_SON].sum);
tree[pos].max_r=max(tree[RIGHT_SON].max_r,tree[LEFT_SON].max_r+tree[RIGHT_SON].sum);
tree[pos].max_all=max(max(tree[LEFT_SON].max_all,tree[RIGHT_SON].max_all),tree[LEFT_SON].max_r+tree[RIGHT_SON].max_l);
tree[pos].sum=tree[LEFT_SON].sum+tree[RIGHT_SON].sum;
}

Complex Ask(int ask_l,int ask_r,int l,int r,int pos)
{
if(ask_l==l&&ask_r==r){
Complex re;
re.max_left=tree[pos].max_l;
re.max_right=tree[pos].max_r;
re.max_=tree[pos].max_all;
re.sum=tree[pos].sum;
return re;
}
int mid=(l+r)>>1;
if(ask_l>mid)
return Ask(ask_l,ask_r,mid+1,r,RIGHT_SON);
if(ask_r<=mid)
return Ask(ask_l,ask_r,l,mid,LEFT_SON);
Complex left=Ask(ask_l,mid,l,mid,LEFT_SON);
Complex right=Ask(mid+1,ask_r,mid+1,r,RIGHT_SON);
Complex re;
re.max_left=max(left.max_left,left.sum+right.max_left);
re.max_right=max(right.max_right,right.sum+left.max_right);
re.max_=max(max(left.max_,right.max_),left.max_right+right.max_left);
re.sum=left.sum+right.sum;
return re;
}

void Modify(int aim,int l,int r,int pos,int num)
{
if(l==r){
tree[pos].max_l=tree[pos].max_r=num;
tree[pos].sum=tree[pos].max_all=num;
return ;
}
int mid=(l+r)>>1;
if(aim<=mid)
Modify(aim,l,mid,LEFT_SON,num);
else
Modify(aim,mid+1,r,RIGHT_SON,num);
tree[pos].max_l=max(tree[LEFT_SON].max_l,tree[RIGHT_SON].max_l+tree[LEFT_SON].sum);
tree[pos].max_r=max(tree[RIGHT_SON].max_r,tree[LEFT_SON].max_r+tree[RIGHT_SON].sum);
tree[pos].max_all=max(max(tree[LEFT_SON].max_all,tree[RIGHT_SON].max_all),tree[LEFT_SON].max_r+tree[RIGHT_SON].max_l);
tree[pos].sum=tree[LEFT_SON].sum+tree[RIGHT_SON].sum;
}

如果有人别出心裁的想用splay来写的话。。。
其实我这道题不会用线段树。。。
我的C++AC代码:
#include<cstdio>
#include<cctype>
#define ch(y , x) C[x].ch[y]
#define par(x) C[x].par
#define v(x) C[x].v
#define s(x) C[x].s
#define lmax(x) C[x].lmax
#define rmax(x) C[x].rmax
#define mmax(x) C[x].mmax
#define sum(x) C[x].sum
#define d(x) C[x].d
const int N = 500010;
const int INF = 1 << 29;
inline int _max(int a , int b)
{
return a > b ? a : b;
}
inline int getint() //读入优化
{
char c = 0;
while(!isdigit(c) && c != '-') c = getchar();
bool down = c == '-';
int tmp = down ? 0 : c - '0';
while(isdigit(c = getchar()))
tmp = (tmp << 1) + (tmp << 3) + c - '0';
return down ? -tmp : tmp;
}
inline int _max(int a , int b , int c)
{
return _max(a , _max(b , c));
}
inline void swap(int &a , int &b)
{
int tmp = a;
a = b;
b = tmp;
}
struct Node
{
int ch[2] , par , v , s , lmax , rmax , mmax , sum;
bool d;
}C[N];
int tot , num[N] , p0 , p1 , root;
void update(int x)
{
int c0 = ch(0 , x) , c1 = ch(1 , x);
s(x) = s(c0) + 1 + s(c1);
sum(x) = sum(c0) + v(x) + sum(c1);
lmax(x) = _max(lmax(c0) , sum(c0) + v(x) + _max(0 , lmax(c1)));
rmax(x) = _max(rmax(c1) , sum(c1) + v(x) + _max(0 , rmax(c0)));
mmax(x) = _max(mmax(c0) , mmax(c1) , _max(0 , lmax(c1)) + v(x) + _max(0 , rmax(c0)));
}
void newnode(int x , int val)
{
ch(0 , x) = ch(1 , x) = par(x) = 0;
v(x) = sum(x) = val;
s(x) = 1;
lmax(x) = rmax(x) = mmax(x) = -INF;
}
void select(int fa , int son , int dd)
{
par(son) = fa;
ch(dd , fa) = son;
d(son) = dd;
}
int build(int tl , int tr)
{
if (tl > tr)
return 0;
int mid = (tl + tr) >> 1;
int q = ++tot;
newnode(q , num[mid]);
select(q , build(tl , mid - 1) , 0);
select(q , build(mid + 1 , tr) , 1);
update(q);
return q;
}
void rot(int x)
{
int p = par(x);
bool dx = d(x);
if (p == root)
par(root = x) = 0;
else
select(par(p) , x , d(p));
select(p , ch(!dx , x) , dx);
select(x , p , !dx);
update(p);
}
void splay(int x , int r)
{
for(register int p = par(x) ; p != r ; p = par(x))
{
if (par(p) == r)
rot(x);
else if (d(p) == d(x))
rot(p) , rot(x);
else
rot(x) , rot(x);
}
update(x);
}
int kth(int k)
{
int i = root , s0;
while(i)
{
s0 = s(ch(0 , i)) + 1;
if (s0 == k)
break;
else if (s0 < k)
k -= s0 , i = ch(1 , i);
else
i = ch(0 , i);
}
return i;
}
void getp(int pos0 , int pos1)
{
p0 = kth(pos0);
splay(p0 , 0);
p1 = kth(pos1);
splay(p1 , p0);
}
int askmax(int tl , int tr)
{
getp(tl , tr + 2);
return mmax(ch(0 , p1));
}
void ins(int pos , int len)
{
getp(pos , pos + 1);
select(p1 , build(1 , len) , 0);
update(p1);
update(p0);
}
void change(int pos , int val)
{
p0 = kth(pos + 1);
v(p0) = val;
splay(p0 , 0);
}
void pretreatment()
{
lmax(0) = rmax(0) = mmax(0) = -INF;
newnode(++tot , -INF);
newnode(++tot , -INF);
select(1 , 2 , 1);
root = 1;
update(root);
par(root) = 0;
}
void dfs(int x = root)
{
if (ch(0 ,x))
dfs(ch(0 , x));
printf("%d " , v(x));
if (ch(1 , x))
dfs(ch(1 , x));
}
int main()
{
int n , m;
register int i;
pretreatment();
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= n ; ++i)
num[i] = getint();
ins(1 , n);
int s , l , r , x;
while(m--)
{
scanf("%d" , &s);
if (s == 1)
{
l = getint() , r = getint();
if (l > r)
swap(l , r);
printf("%d\n" , askmax(l , r));
}
else
{
l = getint() , x = getint();
change(l , x);
}
}
return 0;
}
什么都好，就是常数大。。。
好在可以过这题。

Wa了几遍，找了半天没找到c++的标程
终于A了，发一份在这儿
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 49476 KiB, score = 10

测试数据 #1: Accepted, time = 15 ms, mem = 49476 KiB, score = 10

测试数据 #2: Accepted, time = 46 ms, mem = 49484 KiB, score = 10

测试数据 #3: Accepted, time = 46 ms, mem = 49484 KiB, score = 10

测试数据 #4: Accepted, time = 187 ms, mem = 49480 KiB, score = 10

测试数据 #5: Accepted, time = 312 ms, mem = 49484 KiB, score = 10

测试数据 #6: Accepted, time = 421 ms, mem = 49480 KiB, score = 10

测试数据 #7: Accepted, time = 390 ms, mem = 49484 KiB, score = 10

测试数据 #8: Accepted, time = 421 ms, mem = 49484 KiB, score = 10

测试数据 #9: Accepted, time = 406 ms, mem = 49476 KiB, score = 10

Accepted, time = 2244 ms, mem = 49484 KiB, score = 100

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <math.h>
using namespace std;
const int maxn=500005;
struct jj{
int l,r,sum,lm,rm,maxm;
}tree[maxn*4];
int num[maxn];
int N,M;

void update(int k)
{
tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;
tree[k].lm=max(tree[k*2].lm,tree[k*2].sum+tree[k*2+1].lm);
tree[k].rm=max(tree[k*2+1].rm,tree[k*2].rm+tree[k*2+1].sum);
tree[k].maxm=max(max(tree[k*2].maxm,tree[k*2+1].maxm),tree[k*2].rm+tree[k*2+1].lm);
}

void build_tree(int k,int p,int q)
{
int mid=(p+q)/2;
tree[k].l=p;
tree[k].r=q;
if(p==q){
tree[k].sum=num[p];
tree[k].lm=num[p];
tree[k].rm=num[p];
tree[k].maxm=num[p];
return ;
}
build_tree(k*2,p,mid);
build_tree(k*2+1,mid+1,q);
update(k);
}

jj query(int k,int p,int q)
{
jj a,g,h;
int l,r,mid;
l=tree[k].l;
r=tree[k].r;
mid=(l+r)/2;
if(p==l && q==r) return tree[k];
else if(q<=mid) g=query(k*2,p,q);
else if(p>mid) h=query(k*2+1,p,q);
else{
g=query(k*2,p,mid);
h=query(k*2+1,mid+1,q);
}
if(q<=mid) return g;
else if(p>mid) return h;
else{
a.maxm=max(max(g.maxm,h.maxm),g.rm+h.lm);
a.rm=max(tree[k*2+1].sum+g.rm,tree[k*2+1].rm);
a.lm=max(tree[k*2].lm,tree[k*2].sum+h.lm);
return a;
}
}

void modify(int k,int p,int q)
{
int l,r,mid;
l=tree[k].l;
r=tree[k].r;
mid=(l+r)/2;
if(l==r) {
tree[k].sum=q;
tree[k].maxm=tree[k].lm=tree[k].rm=q;
return ;
}
else if(p<=mid) modify(k*2,p,q);
else if(p>mid) modify(k*2+1,p,q);
update(k);
}

int main()
{
int k,a,b,c;
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++)
scanf("%d",&num[i]);
build_tree(1,1,N);
for(int i=1;i<=M;i++)
{
scanf("%d%d%d",&k,&a,&b);
if(k==1){
if(a>b) {c=a;a=b;b=c;}
printf("%d\n",query(1,a,b).maxm);
}
if(k==2) modify(1,a,b);
}
return 0;
}

此题的出题人有抄袭嫌疑
详见SPOJ GSS3
附上线段树的update关键代码
void update(node &cur,node L,node R)
{
cur.sum=L.sum+R.sum;
cur.lm=max(L.lm,L.sum+R.lm);
cur.rm=max(R.rm,R.sum+L.rm);
cur.om=max(cur.lm,cur.rm);
cur.om=max(cur.om,max(L.om,R.om));
cur.om=max(cur.om,L.rm+R.lm);
}

输出已经改回题目中的格式了。。。。。。。。。。。。。被楼下无限坑，交了7遍。。。。。。。。。。。。。。。。。。。。。。。。。。。。

交了13遍～写了2遍0 0
各种问题，比如sum数组刚开始独立在外的，结果换分数时，没改变sum数组的值，只好整合进线段树
然后就是a>b的，没注意到直接0分。。

直接树状数组嘛，线段树烦不烦。

点击查看程序源码+详细题解

线段树+区间DP。
Lazy的人可以不用lazy标记。
此外输出格式在VIJOS2上又变回WRITELN了。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 88ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：97ms

Gamma机的效率真的是高到爆表了。。。

输出是相邻两个数字之间加一个空格

方法就是线段树维护lmax(该区间从最左端一直向右加的最大值），rmax(该区间从最右端一直向左加的最大值），max(该区间连续段的最大值），s（该区间总和）。会线段树的应该都会写这个题。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 274ms

├ 测试数据 06：答案正确... 867ms

├ 测试数据 07：答案正确... 1257ms

├ 测试数据 08：答案正确... 1288ms

├ 测试数据 09：答案正确... 1288ms

├ 测试数据 10：答案正确... 1054ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：6053ms

邪恶啊。。a>b。。

话说c++程序员被歧视。。没有提示。格式错误，我还以为没输出。。千万要记住输出之间是空格，ac率↓，T-T

时间很难看，估计是用指针的原因

最后庆祝第一题难度4的

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 9ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 353ms

├ 测试数据 06：答案正确... 697ms

├ 测试数据 07：答案正确... 712ms

├ 测试数据 08：答案正确... 822ms

├ 测试数据 09：答案正确... 697ms

├ 测试数据 10：答案正确... 775ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4065ms

我弱……程序跑的慢……

vijos 所测的真的是RP……

0分搞了4回

没注意到存在 a>b。

writeln(ans)

write(ans)

write(ans,' ')

一个一个试终于在最后AC了……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 259ms

├ 测试数据 08：答案正确... 181ms

├ 测试数据 09：答案正确... 166ms

├ 测试数据 10：答案正确... 103ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：709ms

输出格式 是空格 不是换行

题目严重BUG。。。

搞到我WA了一次。。。。。

Accepted 有效得分：100 有效耗时：2321ms

终于对线段树有点感觉了~~

我的核心过程：

procedure pp(var x:re;y,z:re);

begin

with x do

begin

sum:=y.sum+z.sum;

maxn:=max(y.maxn,z.maxn);

maxn:=max(maxn,y.maxl+z.maxr);

maxl:=max(y.maxl+z.sum,z.maxl);

maxr:=max(y.maxr,y.sum+z.maxr);

end;

end;

参考了几位大牛的核心代码，可是感觉有点奇怪，就按照自己的思路做了点修改，

在我的记录中：

l：左子树标识

r：右子树标识

sum：该部分的所有数值之和

maxn：选取该部分的最优解

maxl：将该部分作为左端进行合并时的最优解

maxr：将该部分作为右端进行合并时的最优解

最后按照线段树的方法取maxn就好了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 244ms

├ 测试数据 06：答案正确... 431ms

├ 测试数据 07：答案正确... 494ms

├ 测试数据 08：答案正确... 556ms

├ 测试数据 09：答案正确... 556ms

├ 测试数据 10：答案正确... 509ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2790ms

整整交了10次！

记录编号 Flag 得分 记录信息 环境 评测机 程序提交时间

R1591766 Accepted 100 From mq_miqing－

　P1083 FPC Edogawa Conan 2009-10-8 16:31:20

R1591740 Unaccepted 20 From mq_miqing－

　P1083 FPC Vivid Puppy 2009-10-8 16:26:50

R1591706 Unaccepted 0 From mq_miqing－

　P1083 FPC Vivid Puppy 2009-10-8 16:20:58

R1591695 Unaccepted 0 From mq_miqing－

　P1083 FPC Vivid Puppy 2009-10-8 16:17:46

R1591690 Unaccepted 0 From mq_miqing－

　P1083 FPC Edogawa Conan 2009-10-8 16:16:38

R1589999 Unaccepted 0 From mq_miqing－

　P1083 FPC Vivid Puppy 2009-10-8 0:11:22

R1589997 Unaccepted 0 From mq_miqing－

　P1083 FPC Vag 6K 2009-10-8 0:10:17

R1589902 Unaccepted 0 From mq_miqing－

　P1083 FPC Vivid Puppy 2009-10-7 23:18:20

R1589899 Unaccepted 0 From mq_miqing－

　P1083 FPC Edogawa Conan 2009-10-7 23:17:25

R1589871 Unaccepted 0 From mq_miqing－

　P1083 FPC Vijos Sunny 2009-10-7 23:06:00

比通过率9%还高一个百分点，哈哈。。

140line的线段树，真是经典的题目，就是太麻烦了

不过正好练封装，封装好了代码很漂亮，pascal的内嵌函数、过程有时候用起来很不错，省去很多全局变量，封装效果很好（封装性越好的代码越好写，写起来不累，还可以重复利用，呵呵）

用下划线重复命名函数、过程很专业的样子。。。。呵~~~~~

感谢zbwmqlw神牛帮我标准化我的代码，并在我看错题的时候用看别人玩dota的方式鼓励我依靠自己的力量AC这个题。。。。。。。。

program vijos_1083;

type

TTreeNode=record

l,r,sum,maxL,maxM,maxR:longint

end;

const

maxN=500000;

maxLong=maxLongint>>2;

var

n:longint;

a,f:array[0..maxN] of longint;

tree:array[1..maxN*4] of TTreeNode;

function max(d:array of longint):longint;

var

i:longint;

begin

max:=-maxLong;

for i:=low(d) to high(d) do

if d[i]>max then max:=d[i];

end;

procedure update(i:longint);

begin

tree[i].sum:=tree.sum+tree.sum;

tree[i].maxL:=max([tree.maxL,tree.sum+tree.maxL]);

tree[i].maxM:=max([tree.maxM,tree.maxM,tree.maxR+tree.maxL]);

tree[i].maxR:=max([tree.maxR,tree.sum+tree.maxR]);

end;

procedure makeTree(i,left,right:longint);

var

mid:longint;

begin

with tree[i] do begin

l:=left;

r:=right;

end;

if left=right then

with tree[i] do begin

sum:=a[left];

maxL:=a[left];

maxM:=a[left];

maxR:=a[left];

exit;

end;

mid:=(left+right)>>1;

makeTree(i