1. 项目背景与题目解析P3939 数颜色是信息学奥林匹克竞赛OI中一道经典的数组操作题目。题目要求我们处理一个颜色序列支持两种操作查询某个区间内特定颜色的数量以及交换相邻两个元素的位置。这类问题在实际编程竞赛中非常常见考察选手对基础数据结构的掌握和算法优化能力。题目具体描述如下给定一个长度为n的颜色序列颜色用正整数表示进行m次操作操作分为两种类型查询操作询问区间[l,r]内颜色为c的元素个数交换操作交换位置x和x1的元素对于100%的数据n,m ≤ 3×10^5要求算法时间复杂度控制在O(mlogn)或更好。2. 基础解法与性能分析2.1 暴力解法及其局限性最直观的解法是直接模拟题目要求的操作// 暴力解法示例 vectorint colors(n); for(int i0; im; i){ if(op 1){ // 查询操作 int cnt 0; for(int jl; jr; j){ if(colors[j] c) cnt; } cout cnt endl; } else { // 交换操作 swap(colors[x], colors[x1]); } }这种暴力解法的时间复杂度为查询操作O(r-l1)交换操作O(1)对于n,m都是3×10^5的情况最坏情况下每次都是查询整个区间总时间复杂度会达到O(mn)9×10^10显然无法在合理时间内完成。2.2 数据结构选型思考我们需要选择合适的数据结构来优化查询操作。常见的选择有线段树可以维护区间信息但直接维护每种颜色的计数会导致空间复杂度过高树状数组适合维护前缀和但同样面临颜色种类多的问题平衡树/STL set可以对每种颜色维护位置集合查询时使用lower_bound分块处理将序列分成若干块每块维护颜色计数经过分析使用STL vector存储每种颜色的位置集合是最优选择空间复杂度O(n)查询操作二分查找O(logn)交换操作更新两个元素的位置O(logn)3. 高效解法实现3.1 数据结构设计我们为每种颜色维护一个有序的位置集合unordered_mapint, vectorint color_pos; // 颜色到位置列表的映射 vectorint colors(n); // 原始颜色序列初始化时需要预处理for(int i0; in; i){ cin colors[i]; color_pos[colors[i]].push_back(i1); // 假设位置从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和x1的元素需要注意如果两个位置颜色相同无需操作否则需要更新两个颜色的位置集合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并改为x1 auto it1 lower_bound(vec1.begin(), vec1.end(), x); *it1 x1; // 在c2的位置集合中找到x1并改为x auto it2 lower_bound(vec2.begin(), vec2.end(), x1); *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; vectorint colors(n); unordered_mapint, vectorint color_pos; for(int i0; in; i){ cin colors[i]; color_pos[colors[i]].push_back(i1); // 位置从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 x1; auto it2 lower_bound(vec2.begin(), vec2.end(), x1); *it2 x; swap(colors[x-1], colors[x]); } } return 0; }4. 算法优化与性能分析4.1 时间复杂度分析预处理O(n)只需遍历一次序列查询操作O(logn)两次二分查找交换操作O(logn)两次二分查找加修改总时间复杂度为O((nm)logn)完全满足题目要求。4.2 空间复杂度分析使用unordered_map和vector存储位置信息空间复杂度为O(n)可以接受。4.3 进一步优化思路输入输出优化使用ios::sync_with_stdio(false)和cin.tie(nullptr)加速IO内存分配优化预先估计颜色种类reserve足够空间并行处理如果查询操作很多可以考虑多线程处理独立查询5. 常见错误与调试技巧5.1 边界条件处理位置编号从0还是1开始要保持一致交换操作时x的有效范围检查相同颜色交换时的特判5.2 数据结构选择误区误用multiset虽然可以维护位置但修改操作时间复杂度为O(n)线段树过度设计对于这种特定问题线段树实现复杂且性能未必更优忽略二分查找的前提必须保证位置数组是有序的5.3 调试建议小数据测试先用手算能验证的小数据测试输出中间结果在交换操作前后打印颜色和位置信息对拍测试用暴力算法生成随机数据对比结果6. 竞赛中的实际应用这类问题在竞赛中常见的变体包括带修改的区间查询如区间赋值、区间加等多维查询如二维平面上的颜色统计动态版本维护支持回退到历史版本掌握这种基于颜色分类和二分查找的技巧可以解决许多类似问题。在实际比赛中快速识别问题本质并选择合适的数据结构是关键。