Sleepy Cow Sorting (USACO Gold 2019 January)

观察牛的移动，可以发现FJ在整个过程中能够移动的，就是前 $K$ 头牛。所以比较容易想到， $K$ 头牛之后的所有牛，应该本来就是一个单调增的序列，这样通过移动前 $K$ 头牛，才能变成有序的。例如，如果最初顺序是：

  1 2 4 3

那么最后的单调增序列是不需要动的，这里就是3号牛一头，前面的部分都需要移动，所以需要移动3次。每次就是把第一个数字移动到单调增序列中的合适位置，保持这是一个单调增序列。所以求移动次数 $K$ ，就是通过从后向前扫描和到最长单调增序列长度 $L$ ，就得到 $K=N-L$ 。

题目要求给出移动方案，我们还是观察队列末尾单调增序列的变化，这个序列开始长度是 $N-K$ ，随着每一次移动逐渐变长。因为每个数字只移动一次，所以数字移动到的在这个序列里的位置，是可以计算出来的。这个是一个区间求和问题，就是把 $1..N$ 的线段树中，已经在单调增序列里的数字的位置标成1，其它为0，然后求 $N-1+\text{sum}(x+1, N)$ ，就是当前数字应该移动到的位置，其中 $\text{sum}()$ 是线段树区间求和函数， $x$ 是当前在移动的数字。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
int a[100005];
int tree[200005];       // 线段数
void add(int k, int x) {  // 更新元素k为x
  k += n;
  tree[k] += x;
  for (k /= 2; k >= 1; k /= 2) {
    tree[k] = tree[2*k]+tree[2*k+1];
  }
}
int sum(int a, int b) { // 返回区间[a,b]的和
  a += n; b += n;
  int s = 0;
  while (a <= b) {
    if (a%2 == 1) s += tree[a++];
    if (b%2 == 0) s += tree[b--];
    a /= 2; b /= 2;
  }
  return s;
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        a[i]--;
    }
    int len = 1;
    add(a[n-1], 1);
    for (int i = n-2; i >= 0; i--) {
        if (a[i] > a[i+1]) break;
        len++;      // 结尾单调增序列长度
        add(a[i], 1);
    }
    printf("%d\n", n-len);
    for (int i = 0; i < n-len; i++) {
        if (i) printf(" ");
        printf("%d", n - 1 - sum(a[i]+1, n-1));       // 大于a[i]的元素个数，决定移动到的位置
        add(a[i], 1);
    }
    return 0;
}