模拟赛 6 题解

模拟+贪心+BIT+结论+套路

A . 贪吃蛇

傻逼模拟，运用stl的队列和set判重。

去掉尾巴的时候记得在set里面erase就好了。

B. 分糖果

原题 P2123 皇后游戏。

钦定的大小关系：

$\begin{cases} \min(x.a,y.b)<\min(x.b,y.a)&\min(x.a,y.b)\neq\min(x.b,y.a) \\ x.a<y.a&\min(x.a,y.b)=\min(x.b,y.a) \end{cases}$

第一个证明邻项交换法就好了，推式子。

第二个太神仙至今不会，考虑 $a$ 会对以后影响更多，贪心就好了。

C. 排序

我们可以发现这样的一个性质：在一次操作后，每个元素和它后面产生的逆序对被消除。

因为它回到了相对正确的位置上。

所以单次操作后修改的元素就不用再考虑了，可以删除掉。

每个数只会被删一次。

那么有个naive的想法就是用链表每次暴力跳+删除。

随机数据下表现优秀，但还是 $O(nm)$ 的。

考虑优化这个删除的过程，我们如何避免访问被删除的数。

正解给出了在线段树上二分位置，这样删除是 $O(\log n)$ 的。

神仙wyx给出了另外一种解法：离线树状数组。

我们可以把询问离线下来，搞一棵权值树状数组，其中下标是 $a$，权值是询问的时间。

对于每一个询问位置，我们维护它最早在什么时间询问的。（这之后这个点就没有作用了）

在处理时，我们枚举 $i:1\rightarrow n$，依次处理每个元素的贡献。

一个元素的贡献，一定算在了在它前面，比它大，且第一个出现的元素上面。

这个可以用反向树状数组轻松维护，而我们从 $1$ 到 $n$ 保证了询问在它前面。

查询到某个点时，就把这个点的询问加进去就好了，对前面没有影响。