2020.08.01 2020牛客暑期多校训练营（第七场） prob:4:5:10 rnk:95/1090

20200801比赛记录

2020.08.03 2020牛客暑期多校训练营（第八场） prob:3:4:11 rnk:265/685

20200803比赛记录

暂无。

CF2100-2800泛做1

牛客七、八及cf加训。

来源：CF1326E - Bombs

tag：思维，线段树。

概述：给出长度为 $n$ 的两个排列 $p,q$ ，按照顺序从 $1$ 到 $n$ ，把 $p_i$ 加入集合，如果位置 $i$ 有炸弹则从集合中取出一个最大值，结果是最后集合中的最大值。第 $i$ 个答案回答的是 $q_1,q_2,\ldots q_{i-1}$ 处有炸弹时的结果。

答案：我们观察到答案是单调不上升的，如果答案至多为 $x$ ，我们就需要让 $x+1,x+2,\ldots,n$ 都被炸掉，条件就是对于每个位置右边大于 $x$ 的 $p_i$ 的数量都不多于右边的炸弹数量。可以线段树维护 $右面不小于当前答案的p_i的数量-右面炸弹数量$ ，如果小于等于 $ 0 $ 则减小当前答案。

comments：神奇的转换思维。