洛谷：P7910：插入排序

题目

P7910：插入排序

分析

这道题用来帮助学生理解插入排序的机制。本题的解法用了更高级的STL，不再模拟计算，而是直接通过内置的排序，通过跟踪<value, original_position>来“回答”各个查询。

核心数据结构

我们用到的是set<pair<int, int>>。根据说明，set的特性是排序，无重复，所以我们插入的元素不是简单的数值，而是一个pair，其中的第二个int就是原始的位置——这样，就能保证每个元素都是不同的。

同时，再用另外一个数组pos[MAXN]手动跟踪排序后元素的位置。综合起来用initPositions来完成：

void initPositions()
{
    ordered_set.clear();
    for (int i = 1; i <= n; i++)
    {
        ordered_set.insert({a[i], i});
    }

    // 更新每个元素排序后的位置
    int rank = 1;
    for (auto &p : ordered_set)
    {
        pos[p.second] = rank++;
    }
}

在更新操作时，位置的维护方式与上述初始化类似：先调整集合中的元素，再遍历更新pos数组。

引入STL后可以显著简化实现并提升开发速度，尤其在处理排序与去重场景时更为便捷。但在性能边界（如对数级常数、内存占用）上，仍需根据具体限制权衡。

答案

思考

（无）