本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-12 20:34:57

:::::info[题目基本信息] 考察：ST 表，前缀和，线段树，可持久化线段树，分治（省选/NOI-）。
题目简介： 给定 $n,p$ 以及 $\{h_n\},\{a_n\}$，求有多少个整数对 $(l,r)$ 满足：

• $1\le l,r\le n$
• $\displaystyle\forall k\in[l,r],(\sum_{i=l}^r[i\ne k]\max(0,h_i-a_i))+\max(0,a_i-h_i)\ge p(\sum_{i=l}^r[i\ne k]\max(0,a_i-h_i)+\max(0,h_i-a_i))$

数据范围：

• $1\le n\le 2\times 10^5$
• $1\le p\le 100$
• $\forall i\in[1,n],0\le h_i,a_i\le 10^6$

时间限制：5s。
空间限制：2GB。
::::: 首先，贪心地想，选取的 $k$ 一定满足 $h_k-a_k$ 在 $[l,r]$ 中最大，如果 $\forall i\in[l,r],h_i\le a_i$ 那么不会交换，同时这个区间不会产生贡献。
考虑进行启发式分治，每次选取 $h_k-a_k$ 最大的 $k$，向左右两边分治，同时查询经过 $k$ 的区间的贡献，找到这个 $k$ 显然可以使用 ST 表实现。
现在最大的问题就是怎么计算经过 $k$ 的区间的贡献，先对原条件转化：
$$(\sum_{i=l}^r[i\ne k]\max(0,h_i-a_i))+\max(0,a_i-h_i)\ge p((\sum_{i=l}^r[i\ne k]\max(0,a_i-h_i))+\max(0,h_k-a_k))\\Leftrightarrow (\sum_{i=l}^r[i\ne k]\max(0,h_i-a_i))-(p\sum_{i=l}^r[i\ne k]\max(0,a_i-h_i))\ge p\max(0,h_i-a_i)-\max(0,a_k-h_k)$$ 由于 $h_k>a_k$ 才能产生贡献，所以我们就可以继续转化：
$$(\sum_{i=l}^r[i\ne k]\max(0,h_i-a_i))-p(\sum_{i=l}^r[i\ne k]\max(0,a_i-h_i))\ge p\max(0,h_i-a_i)-\max(0,a_i-h_i)\\Leftrightarrow(\sum_{i=l}^r[i\ne k]\max(0,h_i-a_i))-(p\sum_{i=l}^r[i\ne k]\max(0,a_i-h_i))\ge p(h_k-a_k)$$ 令 $b_i=h_i-a_i$，得到：
$$(\sum_{i=l}^r[i\ne k]\max(0,h_i-a_i))-p(\sum_{i=l}^r[i\ne k]\max(0,a_i-h_i))\ge p(h_k-a_k)\\Leftrightarrow(\sum_{i=l}^r[i\ne k]\max(0,b_i))-p(\sum_{i=l}^r[i\ne k]\max(0,-b_i))\ge pb_k\\Leftrightarrow(\sum_{i=l}^r\max(0,b_i))-p(\sum_{i=1}^r\max(0,-b_i))\ge pb_k$$ 前面这坨可以使用前缀和维护。具体地，设 $\displaystyle sum_i=\sum_{j=1}^i\max(0,b_i)-p\max(0,-b_i)$，那么原式转化为：
$$(\sum_{i=l}^r\max(0,b_i))-p(\sum_{i=1}^r\max(0,-b_i))\ge pb_k\\Leftrightarrow sum_r-sum_{l-1}\ge pb_k$$ 现在这坨看起来就非常舒服，我们重新理一下我们要干什么：统计整数对 $(L,R)$ 的个数，满足：

• $l\le L\le k\le R\le r$

• $sum_R-sum_{L-1}\ge pb_k$

• 当 $k-l\le r-k$ 时，我们枚举 $L$，对 $R$ 的限制条件变为：

  • $k\le R\le r$
  • $sum_R\ge sum_{L-1}+pb_k$

  这就是个二维数点问题，可以使用离线线段树或者在线主席树实现，我使用了主席树。

• 当 $k-l>r-k$ 时，我们枚举 $R$，统计方式同理。

这样我们就做完了这道题。
时间复杂度为 $\Theta(n\log^2 n)$，空间复杂度为 $\Theta(n\log n)$。
:::::success[对启发式分治时间复杂度的一点说明] 启发式合并的复杂度我们都知道，是 $\Theta(n\log n)$ 的，启发式分治就相当于启发式合并的逆过程，复杂度显然相同。 :::::