考场上感觉的确是线段树，还要维护区间最值...最值怎么维护？还要区间修改？(update)的时候加一下就好了吧...之后怎么搞啊？(qwqwq)之后好像不太会了...果断删除几乎快码完的线段树，开始写(20)分暴力...。感觉(20)直接上(O(n^3))算法应该可以。注意到有(20)分是(op=0)，如果数据比较热心控制在(1e5)内，应该可以用(ST)表预处理，拿到就是血赚。--以上是考场心路李辰
最后：(0)分，(qwq)。
原因：可能有负边权，那么用来更新的值（也就是代码中的(sell)）就不能是(0)了，应是负无穷，因为他必须买卖一次的。但是(ans)应该是0.这个问题在数据结构题目中应尤为注意。
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,ans;
int seq[100090];
int sta[100090][30];
void subtask1()
{
for(int i=1;i<=n;i++) scanf("%d",&seq[i]);
for(int i=1;i<=m;i++)
{
int op=0,x=0,y=0,z=0;
scanf("%d",&op);
if(op==1)
{
scanf("%d%d%d",&x,&y,&z);
for(int j=x;j<=y;j++) seq[j]+=z;
}
else if(op==2)
{
ans=0;
scanf("%d%d",&x,&y);
if(x<=y)
{
for(int j=x;j<=y;j++)
{
int sell=-1e9;
for(int k=j+1;k<=y;k++)
sell=max(sell,seq[k]);
ans=max(ans,sell-seq[j]);
}
printf("%d
",ans);
}
else
{
for(int j=x;j>=y;j--)
{
int sell=-1e9;
for(int k=j-1;k>=y;k--)
sell=max(sell,seq[k]);
ans=max(ans,sell-seq[j]);
}
printf("%d
",ans);
}
}
// for(int i=1;i<=n;i++) printf("%d ",seq[i]);
// printf("
");
}
}
int ask_max(int l,int r)
{
int k=log2(r-l+1);
return max(sta[l][k],sta[r-(1<<k)+1][k]);
}
int main()
{
// freopen("wuliangye.in","r",stdin);
// freopen("wuliangye.out","w",stdout);
scanf("%d%d",&n,&m);
if(n<=500&&m<=500) {subtask1();return 0;}
for(int i=1;i<=n;i++) scanf("%d",&sta[i][0]);
for(int j=1;j<=30;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
sta[i][j]=max(sta[i][j-1],sta[i+(1<<(j-1))][j-1]);
for(int i=1;i<=m;i++)
{
int op=0,l=0,r=0;
scanf("%d",&op);
if(op==2)
{
ans=0;
scanf("%d%d",&l,&r);
if(l<=r)
{
for(int j=l;j<=r-1;j++)
ans=max(ans,ask_max(j+1,r)-sta[j][0]);
}
else
{
for(int j=l;j>=r+1;j--)
ans=max(ans,ask_max(r,j-1)-sta[j][0]);
}
printf("%d
",ans);
}
}
return 0;
}
正解：的确是线段树，答案是需要这样维护，对于一个(l<r)的区间，答案是这样更新的：左区间的答案、右区间的答案、跨区间的情况。而跨区间的情况即右儿子的最大值减左儿子的最小值。普通区间维护就行了，因为有两种走法（从左到右，从右到左），那么需要记录两种答案，和区间最大值最小值。
#include<cstdio>
#include<algorithm>
#define maxn 100090
using namespace std;
typedef long long ll;
int n,m;
int val[maxn];
struct Segmenttree{
int l,r;
int lazy,maxx,minn,ans1,ans2;
}t[maxn*4];
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;
if(l==r)
{
t[p].maxx=t[p].minn=val[l];
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
t[p].maxx=max(t[p<<1].maxx,t[p<<1|1].maxx);
t[p].minn=min(t[p<<1].minn,t[p<<1|1].minn);
t[p].ans1=max(max(t[p<<1].ans1,t[p<<1|1].ans1),t[p<<1|1].maxx-t[p<<1].minn);
t[p].ans2=max(max(t[p<<1].ans2,t[p<<1|1].ans2),t[p<<1].maxx-t[p<<1|1].minn);
}
void update(int p)
{
if(!t[p].lazy||t[p].l==t[p].r) return ;
t[p<<1].lazy+=t[p].lazy;
t[p<<1|1].lazy+=t[p].lazy;
t[p<<1].maxx+=t[p].lazy;
t[p<<1].minn+=t[p].lazy;
t[p<<1|1].maxx+=t[p].lazy;
t[p<<1|1].minn+=t[p].lazy;
t[p].lazy=0;
}
void change(int p,int l,int r,int k)
{
update(p);
if(t[p].l==l&&t[p].r==r)
{
t[p].maxx+=k;
t[p].minn+=k;
t[p].lazy+=k;
return ;
}
int mid=(t[p].l+t[p].r)>>1;
if(l>mid) change(p<<1|1,l,r,k);
else if(r<=mid) change(p<<1,l,r,k);
else change(p<<1,l,mid,k),change(p<<1|1,mid+1,r,k);
t[p].maxx=max(t[p<<1].maxx,t[p<<1|1].maxx);
t[p].minn=min(t[p<<1].minn,t[p<<1|1].minn);
t[p].ans1=max(max(t[p<<1].ans1,t[p<<1|1].ans1),t[p<<1|1].maxx-t[p<<1].minn);
t[p].ans2=max(max(t[p<<1].ans2,t[p<<1|1].ans2),t[p<<1].maxx-t[p<<1|1].minn);
}
int query_MAX(int p,int l,int r)
{
update(p);
if(t[p].l==l&&t[p].r==r) return t[p].maxx;
int mid=(t[p].l+t[p].r)>>1;
if(l>mid) return query_MAX(p<<1|1,l,r);
else if(r<=mid) return query_MAX(p<<1,l,r);
else return max(query_MAX(p<<1,l,mid),query_MAX(p<<1|1,mid+1,r));
}
int query_MIN(int p,int l,int r)
{
update(p);
if(t[p].l==l&&t[p].r==r) return t[p].minn;
int mid=(t[p].l+t[p].r)>>1;
if(l>mid) return query_MIN(p<<1|1,l,r);
else if(r<=mid) return query_MIN(p<<1,l,r);
else return min(query_MIN(p<<1,l,mid),query_MIN(p<<1|1,mid+1,r));
}
int ask1(int p,int l,int r)
{
update(p);
if(t[p].l==l&&t[p].r==r) return t[p].ans1;
int mid=(t[p].l+t[p].r)>>1;
if(l>mid) return ask1(p<<1|1,l,r);
else if(r<=mid) return ask1(p<<1,l,r);
else return max(max(ask1(p<<1,l,mid),ask1(p<<1|1,mid+1,r)),query_MAX(p<<1|1,mid+1,r)-query_MIN(p<<1,l,mid));
}
int ask2(int p,int l,int r)
{
update(p);
if(t[p].l==l&&t[p].r==r) return t[p].ans2;
int mid=(t[p].l+t[p].r)>>1;
if(l>mid) return ask2(p<<1|1,l,r);
else if(r<=mid) return ask2(p<<1,l,r);
else return max(max(ask2(p<<1,l,mid),ask2(p<<1|1,mid+1,r)),query_MAX(p<<1,l,mid)-query_MIN(p<<1|1,mid+1,r));
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&val[i]);
build(1,1,n);
for(int i=1;i<=m;i++)
{
int opt=0,l=0,r=0,w=0;
scanf("%d",&opt);
if(opt==1) scanf("%d%d%d",&l,&r,&w),change(1,l,r,w);
else if(opt==2)
{
scanf("%d%d",&l,&r);
if(l==r) printf("0
");
else if(l<r) printf("%d
",ask1(1,l,r));
else if(l>r) printf("%d
",ask2(1,r,l));
}
}
return 0;
}
这题...还是比较简单的啊（!）,考场上码一半放弃了...再写写应该是可以对的啊。线段树这种用左儿子+右儿子+左右儿子交界来更新答案的这种思想应该很常见了啊，还是没熟练用上。