SPOJ 2916 Can you answer these queries V(线段树-分类讨论)
题目链接:http://www.spoj.com/problems/GSS5/
题意:给出一个数列。每次查询最大子段和Sum[i,j],其中i和j满足x1<=i<=y1,x2<=j<=y2,x1<=x2,y1<=y2。
思路:线段树的节点[L,R]保存LMax,RMax,Max,sum,表示左起最大值、右起最大值、区间最大值、区间数字和。更新比较简单。下面说查询。另外设置三个函数,可以查询任意区间[L,R]的最大值,以L开始向右最多到R的最大值、以R开始向左最多到L的最大值,设其分别为Q(L,R),QL(L,R),QR(L,R)。查询分两种情况讨论(设输入数组为d,S[i]表示d的前i项和):
(1)x2>y1: ans=QR(x1,y1)+S[x2-1]-S[y1]+QL(x2,y2);
(2)x2<=y1,那么有x1<=x2<=y1<=y2,则答案为下面三种情况的最大值:
a、x1<=i<=x2<=j<=y2,ans=QR(x1,x2)+QL(x2,y2)-d[x2];
b、x2<=i<=j<=y1,ans=Q(x2,y1);
c、x1<=i<=y1<=j<=y2,ans=QR(x1,y1)+QL(y1,y2)-d[y1]。
struct node
{
int LMax,RMax,Max,sum;
int L,R;
};
node a[N<<2];
int d[N],S[N];
int n;
void pushUp(int t)
{
if(a[t].L==a[t].R) return;
a[t].LMax=max(a[t*2].LMax,a[t*2].sum+a[t*2+1].LMax);
a[t].RMax=max(a[t*2+1].RMax,a[t*2+1].sum+a[t*2].RMax);
a[t].sum=a[t*2].sum+a[t*2+1].sum;
a[t].Max=max3(a[t*2].Max,a[t*2+1].Max,a[t*2].RMax+a[t*2+1].LMax);
}
void build(int t,int L,int R)
{
a[t].L=L;
a[t].R=R;
if(L==R)
{
a[t].sum=d[L];
a[t].LMax=a[t].RMax=a[t].Max=d[L];
return;
}
int mid=(L+R)>>1;
build(t*2,L,mid);
build(t*2+1,mid+1,R);
pushUp(t);
}
int queryL(int t,int L,int R)
{
if(a[t].L==L&&a[t].R==R) return a[t].LMax;
int mid=(a[t].L+a[t].R)>>1;
int ans;
if(R<=mid) ans=queryL(t*2,L,R);
else if(L>mid) ans=queryL(t*2+1,L,R);
else
{
ans=max(queryL(t*2,L,mid),S[mid]-S[L-1]+queryL(t*2+1,mid+1,R));
}
return ans;
}
int queryR(int t,int L,int R)
{
if(a[t].L==L&&a[t].R==R) return a[t].RMax;
int mid=(a[t].L+a[t].R)>>1;
int ans;
if(R<=mid) ans=queryR(t*2,L,R);
else if(L>mid) ans=queryR(t*2+1,L,R);
else
{
ans=max(queryR(t*2,L,mid)+S[R]-S[mid],queryR(t*2+1,mid+1,R));
}
return ans;
}
int query(int t,int L,int R)
{
if(a[t].L==L&&a[t].R==R) return a[t].Max;
int mid=(a[t].L+a[t].R)>>1;
int ans;
if(R<=mid) ans=query(t*2,L,R);
else if(L>mid) ans=query(t*2+1,L,R);
else
{
int x=query(t*2,L,mid);
int y=query(t*2+1,mid+1,R);
ans=max(x,y);
ans=max(ans,queryR(t*2,L,mid)+queryL(t*2+1,mid+1,R));
}
return ans;
}
int cal(int x1,int y1,int x2,int y2)
{
int a,b,c;
if(x2>y1)
{
a=queryR(1,x1,y1);
b=queryL(1,x2,y2);
return a+b+S[x2-1]-S[y1];
}
int ans;
a=queryR(1,x1,x2);
b=queryL(1,x2,y2);
ans=a+b-d[x2];
a=query(1,x2,y1);
ans=max(ans,a);
a=queryR(1,x1,y1);
b=queryL(1,y1,y2);
ans=max(ans,a+b-d[y1]);
return ans;
}
int main()
{
rush()
{
RD(n);
int i;
FOR1(i,n) RD(d[i]),S[i]=S[i-1]+d[i];
build(1,1,n);
int x1,y1,x2,y2;
int m;
RD(m);
while(m--)
{
RD(x1,y1); RD(x2,y2);
PR(cal(x1,y1,x2,y2));
}
}
}
最新文章
- C#socket通信-----多线程
- 解决Android5.0以后DatePicker选择时间无效的bug。
- Learn Spring Framework(continue update...)
- sqlserver 动态行转列
- P1074 靶形数独 - 40
- AStar算法(转载)
- 【JWPlayer】官方JWPlayer去水印步骤
- ASP.NET是如何在IIS下工作的[转]
- 破解 Splish
- 社区O2O,才是未来10年移动互联网最赚钱的项目
- 分享9款很有创意的HTML5动画
- fancybox 无效 失效 直接打开页面, ajax 之后 fancybox对更新的数据无效,Jquery失效 无效
- VS2010类似Eclipse文件查找功能-定位到
- C#拓展练习之模拟键盘录入
- python _thread模块使用
- hdu_2457_DNA repair(AC自动机+DP)
- MySQL &#39;localhost&#39; (10061)解决方法
- 使用django我的第一个简单项目流程
- [CocoaPods]Podfile文件
- 录音 voice record
热门文章
- NYOJ-85 有趣的数 AC 分类: NYOJ 2014-01-17 21:42 240人阅读 评论(0) 收藏
- 威胁远胜“心脏出血”?国外新爆Bash高危安全漏洞
- Codeforces Round #283 (Div. 2)
- Codeforces Round #259 (Div. 2)-D. Little Pony and Harmony Chest
- jQuery1.9.1--attr,prop与val方法源码分析
- javascript设计模式-生成器模式(Builder)
- Level2行情和传统行情的区别
- 动态修改 NodeJS 程序中的变量值
- ZOJ3229 Shoot the Bullet(有源汇的上下界最大流)
- (转)排列算法 Permutation Generation