P12624 [ICPC 2025 NAC] Humans vs AI 题解 / 启发式分治学习笔记
zrl123456
·
·
题解
:::::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) 的，启发式分治就相当于启发式合并的逆过程，复杂度显然相同。
:::::