题解：P12644 [KOI 2024 Round 1] 会议地点
luoguzbh0011
·
·
题解
题目传送门。
思路：
首先想到直接暴力，时间复杂度 O(QN^2 \cdot N!)。
所以，我们的目标是：把时间复杂度降到 O(Q)，也就是单次询问时间复杂度 O(1)。
问题一：单次会议的开销
让我们看一个借来的公式：\displaystyle\sum^{r}_{i = l}\vert X_a - X_i \vert。
如果去掉绝对值，想必大家都能成功化简，但问题是：怎么去掉绝对值。
注意到题面说“人家的坐标按从小到大的顺序排列”,所以上式可以被拆成两个部分：\displaystyle\sum^{a-1}_{i = l}(X_a - X_i) 和 \displaystyle\sum^{r}_{i = a+1}(X_i - X_a)。
化解得 \displaystyle(a - l) \cdot X_a - \sum_{i=l}^{a-1}X_i + \sum_{i=a+1}^{r}X_i - (r - a) \cdot X_a。
求和部分可以用前缀和来做，整个式子时间复杂度 O(1)。
这样，时间复杂度就降为了 O(QN \cdot N!)。
问题二：会议的顺序
由于疲劳度关系到相邻的两个点，所以我们可以画图表示。
接下来我会用题面中的例子来做示范：
若会议召开顺序为 3 \rightarrow 10 \rightarrow 11，画图为：
这时我们注意到，这条线折返了一下，这个折返是无用的。
怎么让它不折返呢？我们只需要使召开顺序从小到大或从大到小排序就行了。
像这样：
这样我们就不用枚举所有排序了，时间复杂度 O(QN)。
问题三：计算最小疲劳度
观察问题二中的图，我们发现一次会议集合的最小疲劳度是最大开销减最小开销。
那如何计算最大开销与最小开销呢？
对于一个下标为 a 的开会地点，设其右边有 x 户人家，左边有 y 户人家，向右移动一户人家会移动 u 个单位，向左移动一户人家会移动 v 个单位。
$a$ 每向左移动一次，开销会增加 $(y - 1 - x) \cdot u$。
随便选一个点，每次在下面三种行动方案中选一种开销最小的一种执行，观察 $a$ 的变化。
+ 不动。
+ 向左移动一次。
+ 向右移动一次。
我们发现，$a$ 最后总是会停在正中间，这就证明，在正中间的人家开会，开销最小。
再做类似的实验，不过，这次找开销最大的人家。
我们又发现，$a$ 最后总是会停在最外侧，这就证明，在最外侧的人家开会，开销最大。
这样我们就可以只计算三户人家了，时间复杂度终于来到了 $O(Q)$。
### 代码
给代码之前，还有一件事要说：题面读入的是坐标，我们要的是下标，所以我们要二分查找下标。
上代码：
```
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
long long n,z[200009],q,h[200009],l,r;//不开 long long 见祖宗
long long hy(long long a){
return (z[a]*(a-l)-(h[a-1]-h[l-1]))+((h[r]-h[a])-z[a]*(r-a));
}
int main(){
cin>>n>>q;
FOR(i,1,n){
cin>>z[i];
h[i]=h[i-1]+z[i];
}
while(q--){
int x,y;
cin>>x>>y;
l=lower_bound(z+1,z+1+n,x)-z; //lower_bound找第一个大于等于x的数，返回地址，-z获得下标
r=upper_bound(z+1,z+1+n,y)-z-1; //upper_bound找第一个大于x的数，-1后就是最后一个小于等于x的数
if(l<=0||l>n||r<=0||r>n||l>=r){ //一定要有，判断区间里是否有人家
cout<<"0\n";
continue;
}
long long maxx=max(hy(l),hy(r));
long long minn=hy(l+(r-l)/2);
cout<<maxx-minn<<"\n";
}
}
```
看在我写了三个小时的份上，点个赞再走呗！