A1165 Sleepy Cow Sorting G

#include <bits/stdc++.h>
using namespace std;

// Sleepy Cow Sorting G（A1165，USACO2019JAN Gold）
//
// 结论：不被移动的奶牛一定是队尾的一段「本来就递增」的后缀，
// 其余奶牛每头恰好移动一次，K = 后缀前面的奶牛数。
//
// 移动步数：c_i = (还没移动的奶牛数) + (已就位且比 p_i 小的奶牛数)
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) cin >> p[i];

    // 找最长递增后缀 p[s..n]；p[1..s-1] 是需要移动的奶牛
    int s = n;
    while (s > 1 && p[s - 1] < p[s]) s--;
    int K = s - 1;

    // 树状数组：维护已经处理过的奶牛编号，统计其中比 x 小的个数
    vector<int> bit(n + 1, 0);
    auto add = [&](int x) {
        for (int i = x; i <= n; i += i & -i) bit[i]++;
    };
    auto query = [&](int x) {
        int res = 0;
        for (int i = x; i > 0; i -= i & -i) res += bit[i];
        return res;
    };

    vector<int> c(K + 1);
    for (int i = 1; i <= K; i++) {
        // 已就位（前面移过的 + 后面不动的那段）里比 p[i] 小的头数
        int smallerBefore = query(p[i] - 1);
        int smallerSuffix = 0;
        {
            // 后缀 p[s..n] 递增，二分求其中比 p[i] 小的个数
            int lo = s, hi = n + 1;
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (p[mid] < p[i]) lo = mid + 1;
                else hi = mid;
            }
            smallerSuffix = lo - s;
        }
        // 还要越过所有还没移动的奶牛，保证下一个正对 FJ 的仍是 p[i+1]
        c[i] = (K - i) + smallerBefore + smallerSuffix;
        add(p[i]);
    }

    cout << K << "\n";
    for (int i = 1; i <= K; i++) cout << c[i] << (i == K ? '\n' : ' ');
    return 0;
}