本帖的定位是卡常历程分享，不是题解，做法可能存在过不去的卡常毒瘤数据，另外假设 hash_map 中元素的插入修改都是 $\Theta(1)$ 时间的话，二维树状数组+hash_map 的时空复杂度应该是比较合格的 $O(n\log^2n)$。

看了一眼题解区、讨论区似乎没有人用二维树状数组过这题，在线做法基本都是树套树起步了。

AC记录

大致思想：

1. 求出初始逆序对数为 ans。

2. 将所有点对 $(i,a[i])$ 当成平面上的点，放到平面上的点集 $S$ 中。

3. 删除 $x$ 时，删除对应的点 $(p[x],x)$，重新评估 ans，即减去平面上点集 $S$ 的子集 $\{(i,j)\big|(i<p[x]\wedge j>x)\vee(i>p[x]\wedge j<x)\}$ 中点的个数。

对于 2. 3. 用二维树状数组维护平面修改、查询操作即可。

注：虽然二维树状数组操作的平面格点至多是 $100000\times 100000$ 的，但是并不是每一个位置都会被访问到，所以可以通过 hash_map 维护二维空间的部分。

这种做法复杂度应该是正确的，但是奈何常数过大，本题对时空常数要求真高，关键的卡常点在于：

①给 std::unordered_map .reserve 一个合适的初始容器大小，太小了会扩容+冲突增加时间消耗，太大了时空都会不降反增。

②如果直接用 [] 访问到 std::unordered_map 中没有的值，std::unordered_map 会插入一个键值，导致普遍的时空损耗增加。可以先 .find 一下看看是不是有这个值，如果没有，返回 $0$ 即可，能够节省时空开销。

卡常过程中还发现 __gnu_pbds::gp_hash_table 替换掉 std::unordered_map 后慢得离谱，本地运行估计几分钟都跑不出来结果（__gnu_pbds::cc_hash_table 也跑不出来结果）。粗略使用搜索引擎后未找到原因和有效处理方法，如有明白人，请不吝赐教。提交记录