题解：CF2051F Joker

· · 题解

F. Joker

本场最后过的这题/xk

实现。

维护集合 pos 表示目前 Joker 可能处在的位置的集合。

每次操作第 x 个位置就是考虑哪些位置可能前移，哪些位置可能后移，哪些位置可能被新加入。

设有 y\in pos，如果 y\lt x 那么 y+1 可能成为新的答案（把 x 位置的卡牌放到第一个）；如果 y\gt x 那么 y-1 可能成为新的答案（把 x 位置的卡牌放到最后一个）；如果有 y=x 那么先从集合中删去 y，把 1 和 n 添加进来。

直接模拟这个过程 TLE on 8。详见 https://codeforces.com/contest/2051/submission/297931501。

分析这个做法的问题，就是一个位置可能本来就在集合里，但是被插进去太多次了。

我们维护两个可能成为答案的集合。分别表示通过 y+1 成为答案或者通过 y-1 成为答案。每次操作在集合中二分出这些位置，把它们全插到 pos 里。每次往 pos 里新插入的时候，判断是否有新的元素可能成为答案。删除的时候判断它是否有机会再次成为答案。

https://codeforces.com/contest/2051/submission/297945489

https://codeforces.com/contest/2051/submission/297946569

https://codeforces.com/contest/2051/submission/297947497

上面是三发不同的初始和加了卡常的版本。