题解思路

问题理解与分析

我们需要计算对于每个区间 $[a,b]$，所有满足 $a \leq i < j \leq b$ 的灵魂对 $(i,j)$ 提供的攻击力之和。

攻击力分为两种：

1. $p_1$ 攻击力：区间 $(i,j)$ 内最大值 $\leq \min(k_i,k_j)$
2. $p_2$ 攻击力：区间 $(i,j)$ 内最大值在 $k_i$ 和 $k_j$ 之间

关键难点：

• 直接枚举所有点对和所有查询会达到 $O(n^2m)$ 复杂度
• 需要利用排列性质和单调栈优化

核心洞察

1. 支配对思想

只有特定的"重要点对"会产生贡献。对于每个位置 $i$，设：

• $L_i$：左边第一个比 $k_i$ 大的位置
• $R_i$：右边第一个比 $k_i$ 大的位置

那么产生贡献的点对主要与这些边界相关。

2. 贡献分类

经过分析，产生贡献的点对主要有三类：

1. 相邻点对：$(i, i+1)$ 提供 $p_1$
2. $p_1$ 贡献：$(L_i, R_i)$ 提供 $p_1$（当 $L_i$ 和 $R_i$ 都存在时）
3. $p_2$ 贡献：$(L_i, i)$ 和 $(i, R_i)$ 提供 $p_2$（当对应边界存在时）

算法框架

阶段1：预处理

1. 计算左右边界：

   • 使用单调栈在 $O(n)$ 时间内计算每个 $i$ 的 $L_i$ 和 $R_i$
   • $L_i$：左边第一个比 $k_i$ 大的位置（不存在则为0）
   • $R_i$：右边第一个比 $k_i$ 大的位置（不存在则为 $n+1$）

2. 生成贡献事件：

   • 对于每个 $i$，生成可能的贡献点对
   • 记录每个点对 $(i,j)$ 的贡献值和类型

阶段2：离线处理查询

使用扫描线+树状数组的方法：

1. 事件排序：

   • 将贡献点对按右端点 $j$ 排序
   • 将查询按右端点 $b$ 排序

2. 扫描线过程：

   • 从 $1$ 到 $n$ 扫描右端点 $r$
   • 当 $r$ 等于某个贡献点对的 $j$ 时，在树状数组的 $i$ 位置加上贡献
   • 当 $r$ 等于某个查询的 $b$ 时，查询树状数组的 $[a,b]$ 区间和

技术细节

1. 贡献点对的具体生成

对于每个位置 $i$：

• 相邻点对：$(i, i+1)$ 贡献 $p_1$
• $p_1$ 贡献：如果 $L_i \neq 0$ 且 $R_i \neq n+1$，则 $(L_i, R_i)$ 贡献 $p_1$
• $p_2$ 贡献：
  • 如果 $L_i \neq 0$，则 $(L_i, i)$ 贡献 $p_2$
  • 如果 $R_i \neq n+1$，则 $(i, R_i)$ 贡献 $p_2$

2. 扫描线实现

维护两个树状数组：

• 一个用于 $p_1$ 类贡献
• 一个用于 $p_2$ 类贡献

3. 正确性证明

为什么这样能覆盖所有贡献？

• $p_1$ 情况：只有当 $(i,j)$ 之间的最大值小于等于端点时产生贡献，这恰好对应 $(L_i, R_i)$ 的情况
• $p_2$ 情况：当区间最大值在端点值之间时，这个最大值一定是某个位置的 $L_i$ 或 $R_i$ 边界

复杂度分析

• 预处理：$O(n)$ 单调栈
• 事件生成：$O(n)$
• 排序：$O(n \log n + m \log m)$
• 扫描线：$O((n+m) \log n)$
• 总复杂度：$O((n+m) \log n)$，可处理最大数据

样例分析

对于样例数据，通过单调栈计算边界：

• $i=1$: $L_1=0, R_1=2$（右边第一个比7大的是9）
• $i=2$: $L_2=0, R_2=6$（右边第一个比9大的是10）
• 等等

然后生成贡献事件，通过扫描线处理查询。

优化技巧

1. 事件合并：相同 $(i,j)$ 的贡献可以合并
2. 内存优化：使用数组而非链表存储事件
3. 常数优化：使用快排和高效的树状数组实现

特殊情况处理

• 边界情况：$L_i=0$ 或 $R_i=n+1$ 时不生成对应贡献
• 相邻点对：直接处理，不通过单调栈
• 空区间：查询 $a=b$ 时答案为0

总结

这道题的关键在于：

1. 问题转化：将复杂的条件转化为支配对计数问题
2. 单调栈应用：高效计算左右边界
3. 离线扫描线：处理多区间查询
4. 贡献分析：正确识别所有产生贡献的点对类型

通过单调栈预处理和扫描线技巧，我们将一个看似 $O(n^2)$ 的问题优化到了 $O(n \log n)$ 的复杂度。