题意:动态最大连续子序列和,静态的题目
分析:nlogn的归并思想。线段树维护结点的三个信息,最大前缀和,最大后缀和,该区间的最大和的两个端点,然后答案是三个的better。书上用pair保存端点,用自带的<来得到最优。
#include <bits/stdc++.h>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
typedef pair<int, int> P;
const int N = 5e5 + 5;
ll sum[N];
struct ST {
int pre[N<<2], suf[N<<2];
P sub[N<<2];
ll get_sum(P p) {
return sum[p.second] - sum[p.first-1];
}
P better(P a, P b) {
ll v1 = get_sum (a), v2 = get_sum (b);
if (v1 != v2) return v1 > v2 ? a : b;
else return a < b ? a : b;
}
void push_up(int l, int r, int rt) {
pre[rt] = better (make_pair (l, pre[rt<<1]), make_pair (l, pre[rt<<1|1])).second; //该区间的最大前缀
suf[rt] = better (make_pair (suf[rt<<1], r), make_pair (suf[rt<<1|1], r)).first; //该区间的最大后缀
sub[rt] = better (sub[rt<<1], sub[rt<<1|1]); //该区间的最大连续和:max (左前缀,右后缀+左前缀,右后缀)
sub[rt] = better (sub[rt], make_pair (suf[rt<<1], pre[rt<<1|1])); //不一定就是最大前缀或最大后缀
}
void build(int l, int r, int rt) {
if (l == r) {
pre[rt] = suf[rt] = l;
sub[rt] = make_pair (l, l);
return ;
}
int mid = (l + r) >> 1;
build (lson); build (rson);
push_up (l, r, rt);
}
P query_pre(int ql, int qr, int l, int r, int rt) {
if (pre[rt] <= qr) return make_pair (l, pre[rt]);
int mid = (l + r) >> 1;
if (qr <= mid) return query_pre (ql, qr, lson);
P p = query_pre (ql, qr, rson); p.first = l;
return better (p, make_pair (l, pre[rt<<1]));
}
P query_suf(int ql, int qr, int l, int r, int rt) {
if (suf[rt] >= ql) return make_pair (suf[rt], r);
int mid = (l + r) >> 1;
if (ql > mid) return query_suf (ql, qr, rson);
P p = query_suf (ql, qr, lson); p.second = r;
return better (p, make_pair (suf[rt<<1|1], r));
}
P query(int ql, int qr, int l, int r, int rt) {
if (ql <= l && r <= qr) return sub[rt];
int mid = (l + r) >> 1;
if (qr <= mid) return query (ql, qr, lson);
if (ql > mid) return query (ql, qr, rson);
P p1 = query_suf (ql, qr, lson); //ql <= mid < qr
P p2 = query_pre (ql, qr, rson); //和push_up一样
P p3 = better (query (ql, qr, lson), query (ql, qr, rson)); //该区间的最大连续和:max (左前缀,右后缀+左前缀,右后缀)
return better (p3, make_pair (p1.first, p2.second));
}
}st; int main(void) {
int n, q, cas = 0;
while (scanf ("%d%d", &n, &q) == 2) {
for (int i=1; i<=n; ++i) {
scanf ("%lld", &sum[i]); sum[i] += sum[i-1];
}
st.build (1, n, 1);
printf ("Case %d:\n", ++cas);
int ql, qr;
while (q--) {
scanf ("%d%d", &ql, &qr);
P ans = st.query (ql, qr, 1, n, 1);
printf ("%d %d\n", ans.first, ans.second);
}
} return 0;
}
线段树(区间合并) LA 3989 "Ray, Pass me the dishes!"的更多相关文章
-
UVA 1400.";Ray, Pass me the dishes!"; -分治+线段树区间合并(常规操作+维护端点)并输出最优的区间的左右端点-(洛谷 小白逛公园 升级版)
"Ray, Pass me the dishes!" UVA - 1400 题意就是线段树区间子段最大和,线段树区间合并,但是这道题还要求输出最大和的子段的左右端点.要求字典序最小 ...
-
SPOJ GSS1_Can you answer these queries I(线段树区间合并)
SPOJ GSS1_Can you answer these queries I(线段树区间合并) 标签(空格分隔): 线段树区间合并 题目链接 GSS1 - Can you answer these ...
-
POJ 3667 Hotel(线段树 区间合并)
Hotel 转载自:http://www.cnblogs.com/scau20110726/archive/2013/05/07/3065418.html [题目链接]Hotel [题目类型]线段树 ...
-
HDU 3911 线段树区间合并、异或取反操作
题目:http://acm.hdu.edu.cn/showproblem.php?pid=3911 线段树区间合并的题目,解释一下代码中声明数组的作用: m1是区间内连续1的最长长度,m0是区间内连续 ...
-
HDU 3911 Black And White(线段树区间合并+lazy操作)
开始以为是水题,结果...... 给你一些只有两种颜色的石头,0为白色,1为黑色. 然后两个操作: 1 l r 将[ l , r ]内的颜色取反 0 l r 计算[ l , r ]内最长连续黑色石头的 ...
-
HYSBZ 1858 线段树 区间合并
//Accepted 14560 KB 1532 ms //线段树 区间合并 /* 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全变成1 2 a b 把[ ...
-
poj3667 线段树 区间合并
//Accepted 3728 KB 1079 ms //线段树 区间合并 #include <cstdio> #include <cstring> #include < ...
-
hdu3911 线段树 区间合并
//Accepted 3911 750MS 9872K //线段树 区间合并 #include <cstdio> #include <cstring> #include < ...
-
线段树(区间合并) POJ 3667 Hotel
题目传送门 /* 题意:输入 1 a:询问是不是有连续长度为a的空房间,有的话住进最左边 输入 2 a b:将[a,a+b-1]的房间清空 线段树(区间合并):lsum[]统计从左端点起最长连续空房间 ...
随机推荐
-
iOS解决NSData转NSString后字符为空
iOS中,将NSData转NSString的一般方法为[[NSString alloc] initWithData:data encoding:NSUTF8StringEncoding];但是当dat ...
-
linux下zip文件解压后乱码解决方案
解决办法一,利用pyton来处理 1.vi uzip文件2.复制一下内容(Python) #!/usr/bin/env python # -*- coding: utf-8 -*- # uzip.py ...
-
pyqt搜索指定信息 github处找到,谢谢这位朋友的帮助了
def tabunqi(self,text): #第一遍添加之后,不提示,当第二次添加相同的数据时,就提示下 text1=str(text) items = self.downwid ...
-
c#游戏进程杀手
我认为写博客还是比较重要的,特别是短时间写出一个含有新知识点的软件.这样总结下这次编程经验和再捋顺一下这次编程思路.首先来谈谈为什么想做这个小程序,一是感觉自己太贪玩想控制一下,二是也锻炼下自己的编程 ...
-
LeetCode - 728. Self Dividing Numbers
A self-dividing number is a number that is divisible by every digit it contains. For example, 128 is ...
-
elasticsearch简单操作(二)
让我们建立一个员工目录,假设我们刚好在Megacorp工作,这时人力资源部门出于某种目的需要让我们创建一个员工目录,这个目录用于促进人文关怀和用于实时协同工作,所以它有以下不同的需求:1.数据能够包含 ...
-
DRF 解析器和渲染器
一,DRF 解析器 根据请求头 content-type 选择对应的解析器就请求体内容进行处理. 1. 仅处理请求头content-type为application/json的请求体 from dja ...
-
LightOJ1004
#include<bits/stdc++.h> using namespace std; int Map[106][106]; int Vis[106][106]; int Num[106 ...
-
BZOJ3510 首都(LCT)
即动态维护树的重心.考虑合并后的新重心一定在两棵树的重心的连线上.于是对每个点维护其子树大小,合并时在这条链的splay上二分即可.至于如何维护子树大小,见https://blog.csdn.net/ ...
-
修改Jenkins的主目录步骤
在使用Jenkins做持续集成过程中,在构建很多次后发现有时在构建的时候系统提示磁盘空间不足,此时检查发现Jenkins的主目录挂载区放在了服务器根目录下,占用空间较大,此时除了对服务器的磁盘进行扩容 ...