题解：P12644 [KOI 2024 Round 1] 会议地点

· · 题解

思路

首先对于每个会议集合，它的疲劳度应该是会议集合里最大的开销值-最小的开销值。

那么对于每个询问的会议集合，它的最大的开销值和最小的开销值怎么算呢？

注：接下来出现的所有 j，l，r 都表示的是 [1,n] 之间的居民点下标。

我们首先可以想到每个居民的开销值可以通过前缀和和后缀和计算出来的：

对于会议地点 j，它在 [l_i, r_i] 范围内的居民点作为参与者时的开销值为 lsum_j-lsum_{l_i-1}-a_j \times (j-l_i+1)+rsum_j-rsum_{r_i-1}-a_j \times (r_i-j+1)。

其中 lsum_i 表示以坐标 0 为会议地点时，包含前 i 个居民点作为参与者时的开销值，rsum_i 表示以坐标 10^9 为会议地点时，包含第 i 个居民点到第 n 个居民点作为参与者时的开销值。

知道了怎么在 O(1) 时间内算出开销值之后，接下来应该思考每个会议集合内的最大开销值和最小开销值怎么算：

首先对于一个会议集合 (l, r) 的居民点 l, l+1, l+2, ... r-1, r 可以考虑如何比较居民点 p 和居民点 p+1 的开销值。

那么怎么比较呢？我们可以想到如果把会议地点由 p 变为 p+1, 那么 p 左边的每个点都需要多走 a_p-a_{p+1} 的路，而 p+1 右边的每个点会少走 a_p-a_{p+1} 的路，因此如果 p 左边的点的数量比 p+1 右边的点的数量少，那么此时会议地点 p+1 的开销值就比会议地点 p 的开销值少，反之亦然。

显然每个会议集合内的最小开销值一定是 [l, r] 内的最中间的那1或2个居民点的开销值（可以想想这个中间点和它两边的点进行比较会怎么样）。

而每个会议集合内的最大开销值是 l 或者 r 居民点的开销值。（可以想想 l, r 与它们旁边的点进行比较会怎么样）。

那么最后就能在 O(1) 内解决一个询问了。

代码

#include <bits/stdc++.h>
using namespace std;
const long long L=1e9;
long long x[200005], lsum[200005], rsum[200005];//开long long
long long getl(long long l, long long r){//前缀和求以l为会议地点，包含[l, r]的居民作为参与者时的开销值
    return lsum[r]-lsum[l-1]-x[l]*(r-l+1);
}
long long getr(long long l, long long r){//后缀和求以r为会议地点，包含[l, r]的居民作为参与者时的开销值
    return rsum[l]-rsum[r+1]-(L-x[r])*(r-l+1);
}
int main(){
    long long n, q, l, r;
    cin >> n >> q;
    for(long long i=1;i <= n;i++){
        cin >> x[i];
        lsum[i]=lsum[i-1]+x[i];
    }
    for(long long i=n;i >= 1;i--){
        rsum[i]=rsum[i+1]+L-x[i];
    }
    for(long long i=1;i <= q;i++){
        cin >> l >> r;
        //二分求出居民点下标的左右界
        r=upper_bound(x+1, x+1+n, r)-x-1;
        l=lower_bound(x+1, x+1+n, l)-x;
        long long mid=(l+r)/2, ma, mi;
        ma=max(getl(l, r), getr(l, r));
        mi=getl(mid, r)+getr(l, mid);
        cout << ma-mi << "\n";
    }
    return 0;
}