我们发现，如果数列的后缀是递增的，那么是可以不用处理的. 由此引申出一种思路：把整个序列分成两个部分，前一个部分是还未排好序的，后一个部分是已经排好序的. 又因为每头牛最多被移动一次（显然每次只能移动队头，最多 n−1n−1n−1 次就可以保证有序了），后缀不用移动，因此，从后往前数第一个不递减的数，1 1~1  它全都得移动（不然移动不了它），它的位置就是最小移动数. 最小移动数求得后，还要求每头牛移动的距离. 这也不难想到，该距离就是当前未排好序的序列的长度 −1-1−1 加上 这个元素应该在排好序的序列中的位置前面元素的数量. 为此应该维护一个最长的上升后缀，每一次插入到这个数在上升后缀应该在的位置. 我们不妨设计 1−n1−n1−n 的数组，其中 111 表示该元素已经在排好序的序列中，000 表示该元素还未排序. 那么我们就可以知道指定元素的“前面元素”的数量了. 也就是说，对于已排好的序列，我们需要一种数据结构，支持计算前缀和和单点修改. 而且 1e51e51e5 的数据规模，复杂度大约在 O(nlogn)O(nlogn)O(nlogn) 左右 不难想到使用树状数组. 然后本题就完成了. 我们主要要学习这题的分段维护思想，分段处理是否排好序的情况，把复杂问题分解为已解决不影响后面操作和未解决两部分，