问题分析

我们需要解决两个主要问题：

1. 区间众数查询：对于每个查询区间 $[l, r]$，找到出现次数最多且编号最小的基因（夯基）
2. 答案序列处理：将所有查询答案组成序列，求所有连续子区间的 $(按位与 + 和)$ 的最大值

算法思路

整体架构

代码根据数据规模采用两种不同的策略：

• 小数据 ($T \leq 6$)：使用分块算法
• 大数据 ($T > 6$)：使用树上启发式合并（DSU on Tree）

方法一：分块算法（solve1）

分块预处理

b = sqrt(n), bc = n / b;  // 块大小和块数量
for (int i = 0; i <= bc; i++) {
    bl[i] = i * b, br[i] = (i + 1) * b - 1;
}

核心思想

1. 预处理每块到末尾的众数：

   • 对每个块 $i$，计算从 $bl[i]$ 到 $n$ 的众数
   • 存储在 Zs[i][j] 中

2. 预处理块内计数：

   • Ap[i][j] 存储前 $i$ 个块中基因 $j$ 的出现次数

3. 查询处理：

   • 同一块内：暴力统计
   • 跨块查询：
     • 暴力处理左右不完整块
     • 中间完整块使用预处理结果
     • 合并三部分结果

方法二：树上启发式合并（solve2）

区间树构建

// 根据区间包含关系构建树
while (stk.size() && q[i].l > q[stk.top()].r)
    stk.pop();
if (stk.empty())
    e[0].push_back(i);
else
    e[stk.top()].push_back(i);
stk.push(i);

DSU on Tree 过程

1. 重儿子选择：选择区间长度最大的儿子作为重儿子
2. 轻子树处理：递归处理并清空计数
3. 重子树处理：保留计数结果
4. 合并操作：将当前区间与重儿子区间差异部分加入计数

答案处理（print_final）

问题转化

对于答案序列 $a_1, a_2, \dots, a_m$，求：

$$\max_{1 \le l \le r \le m} \left[ \left( \bigwedge_{i=l}^{r} a_i \right) + \left( \sum_{i=l}^{r} a_i \right) \right] $$

优化算法

for (int i = 1; i <= m; i++) {
    for (int j = 0; j <= 20; j++) {
        if (Ans[i] & (1 << j)) continue;
        else La[j] = i;  // 记录该位为0的最后位置
    }
    
    for (int j = 0; j <= 21; j++) {
        if (La[j] == i) continue;
        // 计算以i为右端点的最优解
    }
}

关键观察：按位与的值由所有数在该位都为1决定，利用这一性质可以高效枚举。

复杂度分析

分块算法（solve1）

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

树上启发式合并（solve2）

• 树构建：$O(m\log m)$
• DSU on Tree：$O(n\log n)$
• 总复杂度：$O(n\log n + m\log m)$

算法选择依据

测试点范围	算法选择	原因
$T \leq 6$	分块算法	数据规模较小，分块常数小
$T > 6$	树上启发式合并	大数据下更优的复杂度

代码优点

1. 自适应算法选择：根据测试点编号自动选择最优算法
2. 高效区间处理：利用区间包含关系构建树结构
3. 位运算优化：在答案处理中利用位运算性质降低复杂度
4. 内存管理：及时清空临时计数数组，避免内存泄漏

代码总结

本题通过结合分块和树上启发式合并两种算法，高效解决了大规模区间众数查询问题。针对不同的数据特征选择最优策略，体现了算法设计的灵活性。答案处理部分的位运算优化更是展现了对于问题性质的深入理解。

该解法能够处理 $n, m \leq 5\times 10^5$ 的大数据规模，适用于所有测试点。