题解：「ROI 2023 Day1 T3」Рекорды и антирекорды（基于提供代码）

核心思路总览

本题通过 预处理贡献区间 + 树状数组（BIT）维护最值 求解，核心是将“划分两个子序列最大化得分”的问题，转化为“统计元素对得分的贡献并高效查询最值”。整体复杂度为 $O(n\log n)$ 每测试用例，适配大规模数据。

关键概念与预处理

1. 得分贡献分析

• $q$ 的前缀最大值：需严格递增，每个新增元素若大于 $q$ 历史最大值则得分+1。
• $r$ 的前缀最小值：需严格递减，每个新增元素若小于 $r$ 历史最小值则得分+1。
• 核心发现：每个元素的得分贡献，取决于它在两个子序列中的“极值资格”，可通过预处理元素的“影响区间”来量化。

2. 影响区间预处理（tp数组构建）

用有序集合（set）维护已处理元素的坐标，对每个元素 $a[i]$：

• 找到集合中小于 $a[i]$ 的最大元素 $pre$ 和大于 $a[i]$ 的最小元素 $nex$（即前驱、后继）。
• 确定 $a[i]$ 能影响的区间：左侧 $[pre+1, a[i]-1]$ 和右侧 $[a[i]+1, nex-1]$，这些区间内的元素与 $a[i]$ 存在“极值竞争”关系。
• 用树状数组（c数组）统计每个位置的影响次数，最终生成 $tp[i]$ 数组，存储 $a[i]$ 对应的关键区间和贡献值（$get(a[i])+1$）。

核心算法：树状数组维护最值

1. 两个树状数组（aa、bb）的作用

• aa树状数组：维护以“反向坐标”（$n - x + 1$）为索引的最大值，对应 $r$ 子序列的前缀最小值贡献（因 $r$ 需递减，反向后转化为递增查询）。
• bb树状数组：维护以“原坐标”（$x$）为索引的最大值，对应 $q$ 子序列的前缀最大值贡献（$q$ 需递增，直接查询递增序列最值）。

2. 逆序遍历与答案更新

• 从后往前遍历元素（$i$ 从 $n$ 到 $1$），确保处理当前元素时，后续元素的贡献已被树状数组记录。
• 对每个 $i$，遍历 $tp[i]$ 中的关键区间，通过 aa 和 bb 查询对应区间的最大贡献，与当前元素的贡献相加，更新全局答案。
• 遍历结束后，将当前元素 $a[i]$ 分别插入 aa 和 bb，更新树状数组的最值记录。

代码模块解析

1. 基础工具函数

• lowbit：树状数组的核心操作，用于定位索引位置。
• add/get：普通树状数组（c数组）的增减和查询，用于统计元素影响次数。
• BIT结构体（aa、bb）：支持“区间最大值更新”和“区间最大值查询”的树状数组，适配最值维护需求。

2. 预处理tp数组

• 用set维护前驱、后继元素，快速确定影响区间。
• 通过普通树状数组统计每个位置的影响次数，生成 $tp[i]$ 存储关键区间和贡献值，为后续最值查询做准备。

3. 逆序遍历与答案计算

• 初始化两个最值树状数组（aa、bb），逆序遍历每个元素。
• 利用 $tp[i]$ 中的信息，查询aa和bb的最值，更新全局最大得分。
• 将当前元素的贡献插入树状数组，为前序元素的查询提供支持。

复杂度分析

• 预处理阶段：set的插入和查找为 $O(n\log n)$，树状数组的增减和查询为 $O(n\log n)$，整体 $O(n\log n)$。
• 查询阶段：逆序遍历中，每个元素的tp数组遍历为常数次，树状数组的最值查询和更新为 $O(\log n)$，整体 $O(n\log n)$。
• 总复杂度：$O(n\log n)$ 每测试用例，满足所有数据范围要求。

关键结论

本题的核心是将“子序列划分与极值统计”转化为“区间贡献与最值查询”，通过预处理元素的影响区间，结合树状数组高效维护最值，避免了暴力模拟和复杂DP的高复杂度，是一种“预处理+数据结构”的典型优化思路。