补题日志

补题日志

**Codeforces rating：1770 **

• goal：1900

ATcoder rating：1254

• goal：1600

Codeforces Round 915 (Div. 2)

D

不难发现，设当前排列为 \(q_1,q_2\dots q_n\) ，把 \(q_1\) 移到末尾，造成的影响有：

• 对于前缀中 \(\text{mex}_i<q_1\) 的 \(i\) ，移动后不改变它的值。
• 对于前缀中 \(\text{mex}_i>q_1\) 的 \(i\) ，移动后 \(\text{mex}_i=q_1\) 。
• 前缀中不可能存在 \(\text{mex}=q_1\) 的 \(i\)。
• 修改完之后在末尾添加一个 \(n\) 即可。

这样可以用树状数组直接维护每个前缀 \(\text{mex}\) 的出现次数，修改时统计次数+推平即可。

或者采用单调栈维护每个值的出现次数，修改时把大于当前值的暴力合并。

因为段数最多出现 \(n+n\) 次，所以是 \(O(n)\) 的。