「SDOI / SXOI2022」整数序列 题解

问题分析

核心问题

给定序列$a_i$和权重$b_i$，对于每个查询$(x,y)$，我们需要：

1. 构造$c_i$序列：$a_i=x$时为1，$a_i=y$时为-1，其他为0
2. 找到区间$[l,r]$满足$\sum c_i = 0$且区间内存在非零$c_i$
3. 最大化$\sum b_i \cdot [c_i \neq 0]$

关键观察

观察1：问题转化

只考虑$a_i=x$或$a_i=y$的位置，其他位置不影响平衡但可能影响权重。

观察2：前缀和表示

定义前缀和$s_k = \sum_{i=1}^k c_i$，则区间$[l,r]$平衡等价于$s_r = s_{l-1}$。

观察3：权重最大化

我们需要最大化满足$s_i = s_j$的区间$[i+1,j]$中非零位置的$b_i$之和。

算法思路

方法一：根号分治（官方解法）

核心思想：根据数值出现频率采用不同策略。

频率分类：

• 大数值：出现次数$> \sqrt{n}$
• 小数值：出现次数$\leq \sqrt{n}$

处理策略：

1. 大-大查询（两个都是大数值）

   • 这样的数值对数量$O(n)$
   • 预处理所有大数值对的答案
   • 复杂度：$O(n\sqrt{n})$

2. 小-小查询（两个都是小数值）

   • 直接扫描相关位置
   • 复杂度：$O(\sqrt{n})$每次查询

3. 大-小查询（一个大数值，一个小数值）

   • 预处理大数值信息
   • 在线处理小数值
   • 复杂度：$O(\sqrt{n})$每次查询

方法二：双指针扫描

对于小数值对，可以：

1. 合并$x$和$y$的所有位置，按位置排序
2. 维护前缀和与对应的最小前缀权重
3. 扫描过程中更新答案

方法三：哈希优化

使用哈希表记录每个前缀和值对应的：

• 最小前缀权重（用于最大化差值）
• 相关位置信息

算法细节

预处理大数值

对于每个大数值$x$：

1. 预处理其所有位置
2. 对于每个其他数值$y$，预先计算答案
3. 存储结果供查询使用

在线处理小数值

对于小数值对$(x,y)$：

1. 获取$x$和$y$的所有位置
2. 按位置排序构建混合序列
3. 双指针扫描计算最优解

权重计算技巧

在扫描过程中：

• 维护当前前缀和$cur$
• 维护当前累积权重$curs$
• 用$sum[cur]$记录前缀和为$cur$时的最小累积权重
• 答案更新：$ans = \max(ans, curs - sum[cur])$

复杂度分析

时间复杂度

• 预处理：$O(n\sqrt{n})$
• 查询处理：$O(q\sqrt{n})$
• 总复杂度：$O((n+q)\sqrt{n})$

空间复杂度

• 存储每个数值的位置：$O(n)$
• 预处理的大数值对信息：$O(n\sqrt{n})$

实现要点

1. 数值对排序：查询时保证$c[x] \geq c[y]$，减少重复计算

2. 内存管理：

   • 及时释放不需要的数据
   • 使用vector存储位置信息

3. 边界处理：

   • 处理空序列情况
   • 处理所有权重为负的情况
   • 确保区间内存在非零$c_i$

优化策略

优化1：离散化前缀和

前缀和的值域可能很大，但实际不同的值不会超过$O(n)$。

优化2：局部重置

扫描完成后，只重置实际使用过的哈希表位置。

优化3：缓存友好

让频繁访问的数据在内存中连续存储。

特殊性质利用

$b_i = 1$的情况

问题简化为找到最长的平衡区间。

$b_i > 0$的情况

权重总是正的，可以使用更简单的贪心策略。

$b_i$可正可负的一般情况

需要动态维护最小前缀权重。

总结

本题的核心在于通过根号分治平衡预处理和查询的复杂度，关键技巧包括：

1. 问题转化：将区间平衡转化为前缀和相等
2. 频率分析：根据出现频率选择不同算法
3. 双指针扫描：高效处理小数值对
4. 权重维护：动态更新最优解

对于$n \leq 3\times 10^5$，$q \leq 10^6$的数据规模，基于根号分治的解法能够在合理时间内完成计算，是处理此类大规模区间查询问题的典型方法。