解题思路
首先可以确保每一次列的方向一定不会与 \(s\) 到 \(t\) 的方向相反。
不妨设 \(l=\min\{s,t\}\),\(r=\max\{s,t\}\)。
对于每次移动,所花体力值如下:
显然,从 \(l\) 到 \(r\),一定要翻过 \([l,r]\) 间最高的一个,区间最大我们毫不犹豫地选择 ST 表,然后我们思考一下,令 \(h_x=\max\limits_{i\in[l,r]}\{h_i\}\),那么从 \((l,h_l)\) 到 \((x,h_x)\),一定至少花费 \(4\times\max\limits_{i\in[l,r]}\left\{h_i-(h_l+i-l)\right\}=4\times(\max\limits_{i\in[l,r]}\{h_i-i\}-(h_l-l))\) 体力值,所以再用一个 ST 表维护 \(h_i-i\) 的区间最大值。
同理,从 \((r,h_r)\) 至 \((x,h_x)\) 也需要用一个 ST 表维护 \(h_i+i\) 的区间最大值。
令 \(a\) 为 \(\max\limits_{i\in[l,r]}\{h_i\}\),\(b\) 为 \(\max\limits_{i\in[l,r]}\{h_i-i\}\),\(c\) 为 \(\max\limits_{i\in[l,r]}\{h_i+i\}\),则最后的答案为为 \(a - 4\times h_s - h_t + 2 \times (b + c)\),注意是 \(s,t\),不是 \(l,r\)!!!(因为如果是 \(l,r\) 则询问 \(s,t\) 与 \(t,s\) 所得到的答案是一样的,但显然不同)
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
int n, a[N], f[N][20][3];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
f[i][0][0] = a[i];
f[i][0][1] = a[i] - i;
f[i][0][2] = a[i] + i;
}
for(int i = 1; i <= 19; i++) {
for(int j = 1; j + (1 << (i - 1)) <= n; j++) {
f[j][i][0] = max(f[j][i - 1][0], f[j + (1 << (i - 1))][i - 1][0]);
f[j][i][1] = max(f[j][i - 1][1], f[j + (1 << (i - 1))][i - 1][1]);
f[j][i][2] = max(f[j][i - 1][2], f[j + (1 << (i - 1))][i - 1][2]);
}
}
int q;
cin >> q;
while(q--) {
int s, t, s1, t1;
cin >> s >> t;
s1 = s, t1 = t;
if(s > t) {
swap(s, t);
}
int k = log2(t - s + 1);
int a1 = max(f[s][k][0], f[t - (1 << k) + 1][k][0]);
int b1 = max(f[s][k][1], f[t - (1 << k) + 1][k][1]);
int c1 = max(f[s][k][2], f[t - (1 << k) + 1][k][2]);
cout << a1 - 4 * a[s1] - a[t1] + 2 * (b1 + c1) << '\n';
}
return 0;
}
标签:limits,P7974,题解,cin,times,int,max,ST
From: https://www.cnblogs.com/cyf1208/p/17773536.html