题解（分段维护思想）

我们发现，如果数列的后缀是递增的，那么是可以不用处理的.

由此引申出一种思路：把整个序列分成两个部分，前一个部分是还未排好序的，后一个部分是已经排好序的.

又因为每头牛最多被移动一次（显然每次只能移动队头，最多 $n−1$ 次就可以保证有序了），后缀不用移动，因此，从后往前数第一个不递减的数，$1~$ 它全都得移动（不然移动不了它），它的位置就是最小移动数.

最小移动数求得后，还要求每头牛移动的距离. 这也不难想到，该距离就是当前未排好序的序列的长度 $-1$ 加上 这个元素应该在排好序的序列中的位置前面元素的数量.

为此应该维护一个最长的上升后缀，每一次插入到这个数在上升后缀应该在的位置.

我们不妨设计 $1−n$ 的数组，其中 $1$ 表示该元素已经在排好序的序列中，$0$ 表示该元素还未排序. 那么我们就可以知道指定元素的“前面元素”的数量了.

也就是说，对于已排好的序列，我们需要一种数据结构，支持计算前缀和和单点修改.

而且 $1e5$ 的数据规模，复杂度大约在 $O(nlogn)$ 左右
不难想到使用树状数组.

然后本题就完成了.

#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
int n,a[maxn],tree[maxn],ans[maxn];
int lowbit(int x){return x&(-x);}
void add(int x,int k){
	for(int i=x;i<=n;i+=lowbit(i))tree[i]+=k;
}
int query(int x){
	int ret=0;
	for(int i=x;i;i-=lowbit(i))ret+=tree[i];
	return ret;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	int k=0,sum=n;
	while(a[n-k]>a[n-k-1]){
		add(a[n-k],1);//加入有序序列
		sum--;
		k++;
	}
	add(a[n-k],1),sum--;//无论如何，都要把后缀的第一个元素加入，a[n-k]<a[n-k-1]，a[n-k]才是不降后缀的第一个元素
	for(int i=1;i<=sum;i++){
		add(a[i],1);
		ans[i]=sum-i+query(a[i]-1);//求有序序列前缀和
	}
	printf("%d\n",sum);
	for(int i=1;i<=sum;i++){
		printf("%d ",ans[i]);
	}
	return 0;
}

我们主要要学习这题的分段维护思想，分段处理是否排好序的情况，把复杂问题分解为已解决不影响后面操作和未解决两部分，