题目链接:uva 1400 - "Ray, Pass me the dishes!"
题目大意:给定一个长度为n个整数序列,对m次询问作出回答,对于每次询问(a,b),找到两个下标x,y使得x到y的连续和为区间a,b中最大的连续和,如果存在多解优先x小,然后y小。
解题思路:线段树,对于每个节点维护三个线段值:
- max_sub:区间连续最大和
- max_prefix:区间连续前缀最大和
- max_suffix:区间连续后缀最大和
建树的过程维护三个值,查询时只需考虑左右子节点的max_sub,以及两边max_suffix+max_prefix
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)+1)
typedef long long ll;
const int maxn = 500005;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct segment {
int l, r;
ll val;
segment (int l = 0, int r = 0, ll val = 0) {
this->set(l, r, val);
}
void set (int l, int r, ll val) {
this->l = l;
this->r = r;
this->val = val;
}
segment operator + (const segment& u) {
return segment(min(l, u.l), max(r, u.r), val + u.val);
}
bool operator < (const segment& u) const {
if (val != u.val)
return val < u.val;
if (l != u.l)
return l > u.l;
return r > u.r;
}
};
struct Node {
int l, r;
segment max_sub, max_prefix, max_suffix;
} node[4*maxn];
int N, M;
ll arr[maxn], s[maxn];
Node seg_push (Node a, Node b) {
Node ret;
ll suml = s[a.r] - s[a.l-1];
ll sumr = s[b.r] - s[b.l-1];
ret.l = a.l;
ret.r = b.r;
ret.max_sub = max(a.max_suffix + b.max_prefix, max(a.max_sub, b.max_sub));
ret.max_prefix = max(a.max_prefix, segment(a.l, a.r, suml) + b.max_prefix);
ret.max_suffix = max(b.max_suffix, a.max_suffix + segment(b.l, b.r, sumr));
return ret;
}
void build_segTree (int root, int l, int r) {
if (l == r) {
node[root].l = node[root].r = l;
node[root].max_sub.set(l, r, (ll)arr[l]);
node[root].max_prefix.set(l, r, (ll)arr[l]);
node[root].max_suffix.set(l, r, (ll)arr[l]);
return;
}
int mid = (l + r) / 2;
build_segTree(lson(root), l, mid);
build_segTree(rson(root), mid + 1, r);
node[root] = seg_push(node[lson(root)], node[rson(root)]);
}
Node query (int root, int l, int r) {
if (l <= node[root].l && r >= node[root].r)
return node[root];
int mid = (node[root].l + node[root].r) / 2;
if (l <= mid && r > mid)
return seg_push(query(lson(root), l, r), query(rson(root), l, r));
else if (r <= mid)
return query(lson(root), l, r);
else
return query(rson(root), l, r);
}
int main () {
int cas = 1;
while (scanf("%d%d", &N, &M) == 2) {
s[0] = 0;
for (int i = 1; i <= N; i++) {
scanf("%lld", &arr[i]);
s[i] = s[i-1] + arr[i];
}
build_segTree(1, 1, N);
printf("Case %d:\n", cas++);
int l, r;
for (int i = 0; i < M; i++) {
scanf("%d%d", &l, &r);
Node u = query(1, l, r);
printf("%d %d\n", u.max_sub.l, u.max_sub.r);
}
}
return 0;
}
分享到:
相关推荐
示例 2:输出:20解释:按照原来顺序相反的时间做菜 (2*1 + 3*2 + 4*3 = 20)示例 3:输出:0解释:大家都不喜欢这些菜,所以不做任何菜可以
Cast-iron skillets, pots, and Dutch ... It's no longer just for the camper or cowboy-today, it's a staple piece of cookware in any kitchen helmed by a cook who loves good food.,解压密码 share.weimo.info
meal_dishes_detail.csv
5 以元音字母加y结尾的名词,或专有名词以y结尾的,加-s toy-toys, boy-boys, day-days, ray-rays, Henry-Henrys 6 以辅音字母加-o结尾的名词 一般加-es hero-heroes, Negro-Negroes, potato-potatoes, tomato-...
优课UOOC 深圳大学 大学英语3 - 第2章 General Reading Exercises 答案
dishes.rar
export set TMAKEDIR=/dishes/qt/tmake export set TMAKEDIR=/dishes/qt/tmakeexport set TMAKEDIR=/dishes/qt/tmakeexport set TMAKEDIR=/dishes/qt/tmakeexport set TMAKEDIR=/dishes/qt/tmakeexport set TMAKEDIR...
java开发oa办公系统源码 JeeSite 企业信息管理系统基础框架 框架简介 JeeSite 是一个 开源的企业信息管理系统 基础框架。主要定位于“企业信息管理”领域,可用作企业信息管理类系统、网站后台管理类系统等。...
What egg dishes are properly called “omelettes?” Assuming our taste test succeeds, we can answer the question for only one omelette at a time. We may never know whether all omelettes are delicious,...
托盘里的快速启动工具
Android dishes 购物经常用到数量加减,这里封装的一个自定义控件实现该功能
old to buy things. <br>17. A)The man has never seen the woman before. B)The two speakers work for the same company. C)The two speakers work in the same floor. D)The woman is interested ...
insert into t_order_dishes(sOrderNo, dish_id, price, order_num, subtotal, taste_id1, taste_id2, remark, waiter) select @orderNo, dish_id, price, order_num, price*order_num, taste_id1, taste_id2, ...
book-dishes:二手图书交易系统APP服务器端二进制以及无线点餐系统APP服务器端部分源码
触动人心设计优秀的iphone应用,Josh Clark is a designer, developer, and author who helps creative people clear technical hassles to share their ideas with the world. As both speaker and consultant, he...
select * from ax09_Dishes --商品信息表 select * from ax09_ad --广告图片表 select * from ax09_sale --销售情况表 select * from ax09_sysUser --管理员信息表 select * from ax09_Dish_Selects --订单信息表 ...
We can imagine that all the housework, including washing dishes and cleaning the windows and many kinds of things like this, will be done easily and automatically. It is just because we have robots. ...
Kitchen timer app is the first professional cooking timer designed to cook up to 12 dishes at the same time. Forget the traditionally boiled egg timer, now you can cook complex dishes like a real chef...
// "the most important four words for a successful marriage: i'll do the dishes" 在节点上下文中 const decipher = require("./decipher"); const sentence = "gsv nlhg rnkligzmg ulfi dliwh uli z hfxxvhhufo...
dishes znn 小型日式餐厅点菜系统设计与实现 该项目使用maven构建,采用ddd思想设计,使用SpringMVC、Spring、Hibernae三大框架。 domain层实体领域类,application层为业务类,facade层为门面层,controller为控制...