51Nod-1593 公园晨跑

51Nod-1593 公园晨跑

题意

给定一个环,环上有$n$个点,每个点有一个权值$h$代表着如果从$i$到$j$的话,你必须加上$2h_i+2h_j$。并且加上他们之间的距离$L$。并且在环上会有一个区间被占用导致只能从另外一个方向走。

题解

线段树维护区间最大最小值的坐标和特判相同处理。

首先,面对环和方向性,我们可以把环拆成链式。形成一个$[1,n] \cup [1.n]$的区间对于$X,Y$的查找可以看成两种情况,

  • 一种是$X\leq Y$,那么我们寻找的范围就是$[Y+1,X+n-1]$。
  • 对于$X>Y$的情况,我们寻找的范围就是$[Y+1,X-1]$。

定义$d[x]$为$x$点到第一个点的距离(线性)。

对于给定的两个点$X,Y$,我们获得的权值是确定的,为$d[Y]-d[X]+2h[X]+2h[Y]$,我们可以将这个算式分为$X$部分和$Y$部分。于是我们就可以将式子转化为

$target = (d[Y]+2h[Y]) - (d[X]-2h[X])$

这个式子求最大值,就是对于每个点求第一部分的最大值和第二部分的最小值。之后由于$X != Y$,所以对于线段树维护的是区间内最大最小值的坐标。当坐标相同时,寻找次一级的最小值或者次一级的最大值。

AC代码(要加入读入优化)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const ll INF = 1e11;
//head
const int maxn = 2e5 + 10;
ll h[maxn],d[maxn],A[maxn],B[maxn];
int mmax[maxn<<2],mmin[maxn<<2];
template <class T>
bool read(T &x){
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-') op = 1;
else if(c == EOF) return 0;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op) x = -x;
return 1;
}
inline int Max(int a,int b){
return A[a] > A[b] ? a : b;
}
inline int Min(int a,int b){
return B[a] < B[b] ? a : b;
}
inline ll Mmax(ll a,ll b){
return a>b?a:b;
}
int m,n;
void pushup(int rt){
mmax[rt] = Max(mmax[rt<<1],mmax[rt<<1|1]);
mmin[rt] = Min(mmin[rt<<1],mmin[rt<<1|1]);
}
void build(int l,int r,int rt){
if(l==r){
mmax[rt] = l;
mmin[rt] = l;
return ;
}
int mid = (r+l)>>1;
build(lson);build(rson);
pushup(rt);
}
int query_max(int L,int R,int l,int r,int rt){
if(L <= l && r <= R) return mmax[rt];
int mid = (l+r) >> 1;
ll res = 0;
if(L <= mid) res = Max(res,query_max(L,R,lson));
if(mid < R) res = Max(res,query_max(L,R,rson));
return res;
}
int query_min(int L,int R,int l,int r,int rt){
if(L <= l && r <= R) return mmin[rt];
int mid = (l+r) >> 1;
ll res = 0;
if(L <= mid) res = Min(res,query_min(L,R,lson));
if(mid < R) res = Min(res,query_min(L,R,rson));
return res;
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
rep(i,2,n+2) read(d[i]),d[n+i] = d[i];
rep(i,2,n*2+1) d[i] += d[i-1];
rep(i,1,n+1){
ll hh;read(hh);
h[i] = h[i+n] = hh;
}
A[0] = -INF;B[0] = INF;
rep(i,1,n+n+1){
A[i] = 2*h[i] + d[i];
B[i] = d[i] - 2*h[i];
}
build(1,n*2,1);
while(m--){
int l,r;read(l);read(r);
if(l<=r){
int st = query_max(r+1,l+n-1,1,2*n,1);
int ed = query_min(r+1,l+n-1,1,2*n,1);
ll ans;
if(st == ed){
int st1 = Max(query_max(st+1,l+n-1,1,2*n,1),query_max(r+1,st-1,1,2*n,1));
int ed1 = Min(query_min(ed+1,l+n-1,1,2*n,1),query_min(r+1,ed-1,1,2*n,1));
ans = Mmax(A[st] - B[ed1],A[st1] - B[ed]);
}else ans = A[st] - B[ed];
printf("%lld\n",ans);
}else{
int st = query_max(r+1,l-1,1,2*n,1);
int ed = query_min(r+1,l-1,1,2*n,1);
ll ans;
if(st == ed){
int st1 = Max(query_max(st+1,l-1,1,2*n,1),query_max(r+1,st-1,1,2*n,1));
int ed1 = Min(query_min(ed+1,l-1,1,2*n,1),query_min(r+1,ed-1,1,2*n,1));
ans = Mmax(A[st] - B[ed1],A[st1] - B[ed]);
}else ans = A[st] - B[ed];
printf("%lld\n",ans);
}
}
return 0;
}

reference:https://blog.csdn.net/ZLH_HHHH/article/details/74887389