T2插入排序

这个题目可以模拟来做，也可以用树状数组。

考虑到普及组的同学学过树状数组的可能不太多，这里介绍模拟的做法。

这里设计到查询查询元素的原位置，所以用结构体存储值和原来的位置。

题目中有至多5000次的单点修改，每次修改完直接sort()排序时，复杂度为5000 * n * logn，会超时。

熟悉插入排序的话，会发现排序后的元素修改单个元素后的o(n)的时间内就可以完成调整使数组重新有序。单点修改的操作计算量可以优化为 5000 * n.

再结合数据范围来看，查询的次数比较多，而且查询的是原来某个元素排序后的位置，而且这种查询次数在 105 这个级别，所以我们可以把这个数据提前存储下来，从而实现 o(1) 的查询。

这样的话总计算量是 n* logn + 5000 * n + q,结合数据范围看，可以AC。