[USACO2018]Out of Sorts

[USACO2018]Out of Sorts
神仙数论题,重点是分析一下他排序的分割点。膜了题解还是觉得这题很神仙。

题解考虑的是对于每一个数他会被算多少次,也就是他递归的层数
这个我也想过,但是我完全没有思路啊TAT
然后一个数,他的递归层数是多少呢?
显然地,就是剩下他一个的时候
也就是他左边的出现了分隔符,右边也出现了分隔符
于是,问题就转化为,某一个分隔符出现的时间
然后一个点的答案就是两个分隔符取max
考虑一个数i前面的分隔符怎么得到
其实就是所有比i−1i−1小的数,位置的最大值减去i−1i−1
至于为什么,你结合一下我上文说的  ......  查看更多