原题链接: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。