山海经（线段树）题解
原题链接：COGS 775
题目描述：
“南山之首曰鹊山。其首曰招摇之山，临于西海之上，多桂，多金玉。有草焉，其状如韭而青华，其名曰祝余，食之不饥……又东三百里，曰堂庭之山，多棪木，多白猿，多水玉，多黄金。又东三百八十里，曰猨翼之山，其中多怪兽，水多怪鱼，多白玉，多蝮虫，多怪蛇，名怪木，不可以上。……”（其实就是一堆废话）
《山海经》是以山为纲，以海为线记载古代的河流、植物、动物及矿产等情况，而且每一条记录路线都不会有重复的山出现。某天，你的地理老师想重游《山海经》中的路线，为了简化问题，老师已经把每座山用一个整数表示他对该山的喜恶程度，他想知道第a座山到第b座山的中间某段路(i,j)能使他感到最满意，即(i,j)这条路上所有山的喜恶度之和是(c,d)(a<=c<=d<=b)最大值。于是老师便向你请教，你能帮助他吗？（我不能）
值得注意的是，在《山海经》中，第i座山只能到达第i+1座山。（好奇怪的规定）
输入格式:
输入第1行是两个数n,m，表示一共有n座山，m表示老师想查询的数目。
第2行是n个整数，代表n座山的喜恶度，绝对值均小于10000。
以下m行每行有a,b两个数，1<=a<=b<=m，表示第a座山到第b座山。
输出格式:
一共有m行，每行有3个数i,j,s，表示从第i座山到第j座山总的喜恶度为s。
显然，对于每个查询，有a<=i<=j<=b，如果有多组解，则输出i最小的，如果i也相等，则输出j最小的解。
思路：
首先，这道题在审题方面就是一个大坎。如果我们设一个变量mx[i][j]代表由i到j的所有山喜恶度的和，那么我们要求的ans[c][d]则是在众多mx[i]j中再找出一个最大值。如果我们就这么打，每一次查询的时间复杂度是O(ab)，极限数据下单次也会超时，更不用说多组测试数据了。
那么，既然它维护的是区间特殊值，我们就可以想到用线段树求解。我们要维护的是区间上所有子区间和的最大值，所以我们既要维护一个区间的区间和，还要维护答案。我们分析一下，如果把一个区间分为两个子区间，那么最大区间和的位置有几种情况？
很明显，只有这三种。对于前两种来说，只需把左右子树的mx值取一个最大，但是第三种就相当难办。思考一下，这种情况就相当于两个区间拼起来，而这两个区间，一个靠左一个靠右。我们如果想让它们拼接起来的区间最优，就要让它们在满足可以拼接的位置条件下尽可能更优。于是，我定义了mx0和mx1，分别代表靠左区间的最优值和靠右区间的最优值。那mx0和mx1如何由它的子区间推知呢？我们先假设它的两个子区间的mx0，mx1都已经确定，那么左区间的mx0绝对是一种情况，还有就是左区间的总和sm加上右区间的mx0。同理，mx1也应考虑右区间mx0与右区间mx1加左区间mx1。由于mx不考虑位置问题，那么mx绝对不小于mx0和mx1。这样就可以完成这道题的主体部分。至于输出路径，只需在每次更新mx时更新一下就好了。
代码：
#include<bits/stdc++.h>
using namespace std;
struct node
{
int begin,end;//原区间的位置
int sm;//区间和
int mx,l,r;//总的最大值及其位置
int mx0,l0,r0;//靠左的最大值及其位置
int mx1,l1,r1;//靠右的最大值及其位置
}str[400004];//线段树
int a,b,c[100001],u,v;
inline int lft(int x)
{
return x<<1;//找左区间编号
}
inline int iht(int x)
{
return x<<1|1;//找右区间编号
}
void makstr(int x,int m,int n)//建树
{
if(m>n)
{
return;
}
str[x].begin=m;
str[x].end=n;
if(m==n)
{
str[x].mx=c[m];
str[x].mx0=c[m];
str[x].mx1=c[m];
str[x].sm=c[m];
str[x].l0=m;
str[x].l1=m;
str[x].l=m;
str[x].r0=n;
str[x].r1=n;
str[x].r=n;
return;//对单点区间的操作
}
else
{
int h=(m+n)>>1;//下面递归
makstr(lft(x),m,h);
makstr(iht(x),h+1,n);
str[x].sm=str[lft(x)].sm+str[iht(x)].sm;//求和
if(str[lft(x)].mx>=str[iht(x)].mx)//先把两个子区间比较一下
{
str[x].mx=str[lft(x)].mx;
str[x].l=str[lft(x)].l;
str[x].r=str[lft(x)].r;
//mx相等时很明显左区间的左右边界都更小
}
else
{
str[x].mx=str[iht(x)].mx;
str[x].l=str[iht(x)].l;
str[x].r=str[iht(x)].r;
}
str[x].l0=str[x].begin;//固定的边界
if(str[lft(x)].mx0>=str[lft(x)].sm+str[iht(x)].mx0)//找它的mx0
{
str[x].mx0=str[lft(x)].mx0;
str[x].r0=str[lft(x)].r0;
//mx0相等时很明显不包含右区间的情况右边界更小
}
else
{
str[x].mx0=str[lft(x)].sm+str[iht(x)].mx0;
str[x].r0=str[iht(x)].r0;
}
str[x].r1=str[x].end;//固定的边界
if(str[iht(x)].mx1>str[iht(x)].sm+str[lft(x)].mx1)//找它的mx1
{
str[x].mx1=str[iht(x)].mx1;
str[x].l1=str[iht(x)].l1;
}
else
{
str[x].mx1=str[iht(x)].sm+str[lft(x)].mx1;
str[x].l1=str[lft(x)].l1;
//mx1相等时很明显包含左区间的情况左边界更小
}
if(str[x].mx<str[lft(x)].mx1+str[iht(x)].mx0)//找第三种情况
{
str[x].mx=str[lft(x)].mx1+str[iht(x)].mx0;
str[x].l=str[lft(x)].l1;
str[x].r=str[iht(x)].r0;
}
else
{
if(str[x].mx==str[lft(x)].mx1+str[iht(x)].mx0)//判断是否修改位置
{
if(str[x].l>str[lft(x)].l1)
{
str[x].l=str[lft(x)].l1;
str[x].r=str[iht(x)].r0;
}
else
{
if(str[x].l==str[lft(x)].l1&&str[x].r>str[iht(x)].r0)
{
str[x].r=str[iht(x)].r0;
}
}
}
}
}
}
node foudstr(int x,int m,int n)//找值
{
if(m==str[x].begin&&n==str[x].end)//递归边界
{
return str[x];
}
else
{
int h=(str[x].begin+str[x].end)>>1;//下面是递归
if(n<=h)
{
return foudstr(lft(x),m,n);
}
if(m>h)
{
return foudstr(iht(x),m,n);
}
node j=foudstr(lft(x),m,h),k=foudstr(iht(x),h+1,n),o;
//以下一部分和上面很相似
o.begin=m;
o.end=n;
if(j.mx>k.mx)
{
o.mx=j.mx;
o.l=j.l;
o.r=j.r;
}
else
{
if(j.mx==k.mx)
{
o.mx=j.mx;
o.l=j.l;
o.r=j.r;
}
else
{
o.mx=k.mx;
o.l=k.l;
o.r=k.r;
}
}
o.l0=o.begin;
if(j.mx0>j.sm+k.mx0)
{
o.mx0=j.mx0;
o.r0=j.r0;
}
else
{
if(j.mx0==j.sm+k.mx0)
{
o.mx0=j.mx0;
o.r0=j.r0;
}
else
{
o.mx0=j.sm+k.mx0;
o.r0=k.r0;
}
}
o.r1=o.end;
if(k.mx1>k.sm+j.mx1)
{
o.mx1=k.mx1;
o.l1=k.l1;
}
else
{
if(k.mx1==k.sm+j.mx1)
{
o.mx1=k.sm+j.mx1;
o.l1=j.l1;
}
else
{
o.mx1=k.sm+j.mx1;
o.l1=j.l1;
}
}
if(o.mx<j.mx1+k.mx0)
{
o.mx=j.mx1+k.mx0;
o.l=j.l1;
o.r=k.r0;
}
else
{
if(o.mx==j.mx1+k.mx0)
{
if(o.l>j.l1)
{
o.l=j.l1;
o.r=k.r0;
}
else
{
if(o.l==j.l1)
{
if(o.r>k.r0)
{
o.r=k.r0;
}
}
}
}
}
return o;
}
}
int main()
{
scanf("%d%d",&a,&b);
for(int i=1;i<=a;i++)
{
scanf("%d",&c[i]);
}
makstr(1,1,a);
for(int i=1;i<=b;i++)
{
scanf("%d%d",&u,&v);
node nd=foudstr(1,u,v);
printf("%d %d %d\n",nd.l,nd.r,nd.mx);
}
return 0;
}
总结：
这道题当时我打了一天，主要是因为维护的12个变量是真的想不到。针对最大区间和的情况也想了很久。尤其是最后mx0和mx1不能和mx再进行比较。但是，打完了这道题以后再反过来从理论层面分析一下，发现也并不是非常难。思路通了以后，代码复杂度再高也只需Ctrl+V。