codeforces 515e Drazil and Park 线段树、区间最大子段和

68 阅读 0 评论 45 点赞

我是靠谱客的博主欣慰棒球，最近开发中收集的这篇文章主要介绍codeforces 515e Drazil and Park 线段树、区间最大子段和，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

在一个公园里，有n棵树围成一个圈。每棵树的高度h以及相邻两棵树的距离d已给出。

现在要选择两棵不同的树，使得2*(h1+h2)+dis(d1,d2)的值最大。

每次询问都给出一个区间，所给的区间有小孩子在玩耍，因此不能进入。

1.l <= r，则[l,r]不能进入；

2.l > r，则[1,r]和[l,n]不能进入;

数据保证剩余的至少有两棵树是可以被选择的。

思路：

区间最大子段和，线段树解决。

首先把环转成线性，例如有5个节点，则转换后有10个节点。

1 2 3 4 5 6 7 8 9 10

若l<=r，则询问[r+1,l+n-1]区间；

若l>r，则询问[r+1,l-1]区间。

线段树每个节点保存三个变量：

1.到达右端点的最大值下标；

2.到达左端点的最大值下标；

3.该区间的最大子段和。

区间合并时更新变量，可以查看下面链接中分治法的思想。

http://blog.csdn.net/niteip/article/details/7444973

code:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;
typedef long long LL;
#define root 1, n<<1, 1
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
struct PP {
int cr, cl;
//index
LL val;
}st[N<<3];
int n, m;
LL d[N<<1], h[N<<1];
LL sum[N<<1];
//when query
LL ans;
int idx;
inline LL getdis(int x, int y) {
if(x > y) swap(x, y);
return sum[y-1]-sum[x-1];
}
void pushup(int l, int r, int rt) {
int mid = (l+r)/2;
//right
LL tmp = 2*h[st[rt<<1].cr]+getdis(st[rt<<1].cr, r);
if(tmp > 2*h[st[rt<<1|1].cr]+getdis(st[rt<<1|1].cr, r))
st[rt].cr = st[rt<<1].cr;
else
st[rt].cr = st[rt<<1|1].cr;
//left
tmp = 2*h[st[rt<<1|1].cl]+getdis(st[rt<<1|1].cl, l);
if(tmp > 2*h[st[rt<<1].cl]+getdis(st[rt<<1].cl, l))
st[rt].cl = st[rt<<1|1].cl;
else
st[rt].cl = st[rt<<1].cl;
//val
st[rt].val = max(st[rt<<1].val, st[rt<<1|1].val);
tmp = 2*(h[st[rt<<1].cr]+h[st[rt<<1|1].cl])+getdis(st[rt<<1].cr, st[rt<<1|1].cl);
st[rt].val = max(st[rt].val, tmp);
}
void build(int l, int r, int rt) {
if(l == r) {
st[rt] = (PP){l, r, 2*h[l]};
return ;
}
int mid = (l+r)/2;
build(lson);
build(rson);
pushup(l, r, rt);
}
void query(int l, int r, int rt, int x, int y) {
if(x <= l && y >= r) {
ans = max(ans, st[rt].val);
LL tmp;
if(idx != -1) {
ans = max(ans, 2*(h[idx]+h[st[rt].cl])+getdis(idx, st[rt].cl));
tmp = 2*h[idx]+getdis(idx, r);
if(tmp < 2*h[st[rt].cr]+getdis(st[rt].cr, r))
idx = st[rt].cr;
}
else
idx = st[rt].cr;
return ;
}
int mid = (l+r)/2;
if(x <= mid)
query(lson, x, y);
if(y > mid)
query(rson, x, y);
}
int main() {
scanf("%d%d", &n, &m);
int tmp;
for(int i = 1;i <= n; i++) {
scanf("%I64d", &d[i]);
d[i+n] = d[i];
}
for(int i = 1;i <= 2*n; i++) {
sum[i] = sum[i-1]+d[i];
}
for(int i = 1;i <= n; i++) {
scanf("%I64d", &h[i]);
h[i+n] = h[i];
}
build(root);
//
int l, r;
for(int i = 1;i <= m; i++) {
scanf("%d%d", &l, &r);
ans = 0, idx = -1;
l <= r? query(root, r+1, l+n-1):query(root, r+1, l-1);
printf("%I64dn", ans);
}
return 0;
}