OI经典题解析：高效处理数组颜色查询与交换操作

1. 项目背景与题目解析

P3939 "数颜色"是信息学奥林匹克竞赛（OI）中一道经典的数组操作题目。题目要求我们处理一个颜色序列，支持两种操作：查询某个区间内特定颜色的数量，以及交换相邻两个元素的位置。这类问题在实际编程竞赛中非常常见，考察选手对基础数据结构的掌握和算法优化能力。

题目具体描述如下：

• 给定一个长度为n的颜色序列（颜色用正整数表示）
• 进行m次操作，操作分为两种类型：
  1. 查询操作：询问区间[l,r]内颜色为c的元素个数
  2. 交换操作：交换位置x和x+1的元素

对于100%的数据，n,m ≤ 3×10^5，要求算法时间复杂度控制在O(mlogn)或更好。

2. 基础解法与性能分析

2.1 暴力解法及其局限性

最直观的解法是直接模拟题目要求的操作：

// 暴力解法示例 vector<int> colors(n); for(int i=0; i<m; i++){ if(op == 1){ // 查询操作 int cnt = 0; for(int j=l; j<=r; j++){ if(colors[j] == c) cnt++; } cout << cnt << endl; } else { // 交换操作 swap(colors[x], colors[x+1]); } }

这种暴力解法的时间复杂度为：

• 查询操作：O(r-l+1)
• 交换操作：O(1)

对于n,m都是3×10^5的情况，最坏情况下（每次都是查询整个区间），总时间复杂度会达到O(mn)=9×10^10，显然无法在合理时间内完成。

2.2 数据结构选型思考

我们需要选择合适的数据结构来优化查询操作。常见的选择有：

1. 线段树：可以维护区间信息，但直接维护每种颜色的计数会导致空间复杂度过高
2. 树状数组：适合维护前缀和，但同样面临颜色种类多的问题
3. 平衡树/STL set：可以对每种颜色维护位置集合，查询时使用lower_bound
4. 分块处理：将序列分成若干块，每块维护颜色计数

经过分析，使用STL vector存储每种颜色的位置集合是最优选择：

• 空间复杂度：O(n)
• 查询操作：二分查找O(logn)
• 交换操作：更新两个元素的位置O(logn)

3. 高效解法实现

3.1 数据结构设计

我们为每种颜色维护一个有序的位置集合：

unordered_map<int, vector<int>> color_pos; // 颜色到位置列表的映射 vector<int> colors(n); // 原始颜色序列

初始化时需要预处理：

for(int i=0; i<n; i++){ cin >> colors[i]; color_pos[colors[i]].push_back(i+1); // 假设位置从1开始编号 }

3.2 查询操作实现

查询区间[l,r]内颜色c的数量，可以通过两次二分查找实现：

auto& pos = color_pos[c]; int left = lower_bound(pos.begin(), pos.end(), l) - pos.begin(); int right = upper_bound(pos.begin(), pos.end(), r) - pos.begin(); cout << right - left << endl;

3.3 交换操作实现

交换位置x和x+1的元素需要注意：

1. 如果两个位置颜色相同，无需操作
2. 否则需要更新两个颜色的位置集合

if(colors[x-1] == colors[x]) continue; // 位置从1开始编号 int c1 = colors[x-1], c2 = colors[x]; auto& vec1 = color_pos[c1]; auto& vec2 = color_pos[c2]; // 在c1的位置集合中找到x并改为x+1 auto it1 = lower_bound(vec1.begin(), vec1.end(), x); *it1 = x+1; // 在c2的位置集合中找到x+1并改为x auto it2 = lower_bound(vec2.begin(), vec2.end(), x+1); *it2 = x; // 交换实际颜色值 swap(colors[x-1], colors[x]);

3.4 完整代码实现

#include <iostream> #include <vector> #include <algorithm> #include <unordered_map> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> colors(n); unordered_map<int, vector<int>> color_pos; for(int i=0; i<n; i++){ cin >> colors[i]; color_pos[colors[i]].push_back(i+1); // 位置从1开始 } while(m--){ int op; cin >> op; if(op == 1){ int l, r, c; cin >> l >> r >> c; auto& pos = color_pos[c]; int left = lower_bound(pos.begin(), pos.end(), l) - pos.begin(); int right = upper_bound(pos.begin(), pos.end(), r) - pos.begin(); cout << right - left << endl; } else { int x; cin >> x; if(x < 1 || x >= n || colors[x-1] == colors[x]) continue; int c1 = colors[x-1], c2 = colors[x]; auto& vec1 = color_pos[c1]; auto& vec2 = color_pos[c2]; auto it1 = lower_bound(vec1.begin(), vec1.end(), x); *it1 = x+1; auto it2 = lower_bound(vec2.begin(), vec2.end(), x+1); *it2 = x; swap(colors[x-1], colors[x]); } } return 0; }

4. 算法优化与性能分析

4.1 时间复杂度分析

• 预处理：O(n)，只需遍历一次序列
• 查询操作：O(logn)，两次二分查找
• 交换操作：O(logn)，两次二分查找加修改

总时间复杂度为O((n+m)logn)，完全满足题目要求。

4.2 空间复杂度分析

使用unordered_map和vector存储位置信息，空间复杂度为O(n)，可以接受。

4.3 进一步优化思路

1. 输入输出优化：使用ios::sync_with_stdio(false)和cin.tie(nullptr)加速IO
2. 内存分配优化：预先估计颜色种类，reserve足够空间
3. 并行处理：如果查询操作很多，可以考虑多线程处理独立查询

5. 常见错误与调试技巧

5.1 边界条件处理

• 位置编号从0还是1开始要保持一致
• 交换操作时x的有效范围检查
• 相同颜色交换时的特判

5.2 数据结构选择误区

1. 误用multiset：虽然可以维护位置，但修改操作时间复杂度为O(n)
2. 线段树过度设计：对于这种特定问题，线段树实现复杂且性能未必更优
3. 忽略二分查找的前提：必须保证位置数组是有序的

5.3 调试建议

1. 小数据测试：先用手算能验证的小数据测试
2. 输出中间结果：在交换操作前后打印颜色和位置信息
3. 对拍测试：用暴力算法生成随机数据对比结果

6. 竞赛中的实际应用

这类问题在竞赛中常见的变体包括：

1. 带修改的区间查询：如区间赋值、区间加等
2. 多维查询：如二维平面上的颜色统计
3. 动态版本维护：支持回退到历史版本

掌握这种基于颜色分类和二分查找的技巧，可以解决许多类似问题。在实际比赛中，快速识别问题本质并选择合适的数据结构是关键。