SPOJ GSS1 静态区间求解最大子段和
2024-09-01 01:32:48
题目大意:
给定n个数,再给q个区间询问,希望在区间s,t中找到一段连续的子序列使其和最大
因为询问上万,节点数50000,明显是用线段树去做,这里很明显的区间更新,唯一写起来有点恶心的是询问
每一个区间的最大都要跟左右区间的左最大右最大有关系
反正时要注意细节了,查询的时候同时要查询其左右连续最大
自己的错误在于左右连续最大的更新出问题,这个希望自己以后要注意
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
using namespace std; const int INF = 0x3fffffff;
#define N 50010
#define MOD 100007
#define ls o<<1
#define rs o<<1|1
#define define_m int m=(l+r)>>1 int ml[N*] , mr[N*] , mx[N*] , sum[N*];
int a[N] , pre[N] , n; void push_up(int o)
{
mx[o] = max(mx[ls] , mx[rs]);
mx[o] = max(mx[o] , ml[rs]+mr[ls]);
ml[o] = max(ml[ls],sum[ls]+ml[rs]) , mr[o] = max(mr[rs],sum[rs]+mr[ls]);
sum[o] = sum[ls]+sum[rs];
} void build(int o , int l , int r)
{
if(l==r){
sum[o]=ml[o]=mr[o]=mx[o]=a[l];
return;
}
define_m;
build(ls , l , m);
build(rs , m+ , r);
push_up(o);
} void query(int o , int l , int r , int s , int t , int &ansl , int &ansr , int &ans)
{
if(l>=s && r<=t){
ans = mx[o];
ansl = ml[o];
ansr = mr[o];
return ;
}
define_m;
if(m>=t) query(ls , l , m , s , t , ansl , ansr , ans);
else if(m<s) query(rs , m+ , r , s , t , ansl , ansr ,ans);
else{
int t1,t2,t3,t4,t5,t6;
query(ls , l , m , s , m , t1 , t2 , t3);
query(rs , m+ , r , m+ , t , t4 , t5 , t6);
ansl = max(t1 , pre[m]-pre[s-]+t4) , ansr = max(t5 , pre[t]-pre[m]+t2);
ans = max(t3 , t6);
ans = max(ans , t2+t4);
}
//cout<<o<<" "<<l<<" "<<r<<" "<<s<<" "<<t<<" "<<ansl<<" "<<ansr<<" "<<ans<<endl;
} int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in" , "r" , stdin);
#endif // ONLINE_JUDGE
while(~scanf("%d" , &n))
{
for(int i= ; i<=n ; i++){
scanf("%d" , a+i);
pre[i] = pre[i-]+a[i];
}
build( , , n);
int m;
scanf("%d" , &m);
for(int i= ; i<m ; i++){
int s , t;
scanf("%d%d" , &s , &t);
int t1,t2,t3;
query(,,n,s,t,t1,t2,t3);
printf("%d\n" , t3);
}
}
return ;
}
最新文章
- IOS 二维码的实现
- 深入理解javascript---如何编写高质量的代码?
- PAT 1005. 继续(3n+1)猜想 (25) JAVA
- 国内优秀Android学习资源
- hdu 5306 优先队列
- 八、CCMenu和CCMenuItem
- 临时文档9--dfs
- 负载均衡LVS集群详解
- SE 2014年5月9日
- AngularJS高级程序设计读书笔记 -- 过滤器篇
- java_弹球小游戏
- AI-2.梯度下降算法
- MYSQL 事务和用户权限
- java数组的定义
- 【js】JSDoc 注释规范
- vue环境配置 vue-cli脚手架
- 《Two Dozen Short Lessons in Haskell》所有习题的索引
- C++有关 const &; 内敛 &; 友元&;静态成员那些事
- Cocos Creator学习目录
- SQL之to_date()以及关于日期处理的详解
热门文章
- sqlserver中对时间类型的字段转换
- Normalize.css 与 reset.css
- Process and Thread
- Java 中System里getProperty(something)
- Shell.xaml
- JAVA基础知识之NIO——Buffer.Channel,Charset,Channel文件锁
- JS加密库Crypto-JS SEA加密
- 2016年江西理工大学C语言程序设计竞赛(初级组)
- SelectMany等LINQ运算符的使用
- Flowplayer-Embedding