这题是树状数组好题，竟然是紫题，但是既然是教练的，我就写篇题解吧。

我是学了线段树又学的树状数组，以后永远不写线段树了，而且还比线段树快，教练让我们痛苦了那么长时间，wtnl。

关于树状数组：

不会树状数组的可以戳这里做一下模板。但是我稍微BB两句

树状数组就是巧妙地运用了lowbit函数，表示离父亲还有多少步。此处lowbit就是转换二进制，然后取反，之后加一，这就是lowbit。

定一个c数组维护这个数列上某个区间的和。

这样造出了一棵树，单点修改就是沿着树往右走，修改所有的c。

此处单点修改和区间查询复杂度都是$O(log n)$，建树复杂度$O(n log n)$常数比线段树都小。

这题思路：

只要数列中逆序对 $i<j$ && $p_i>p_j$ 那么就需要往后移动。 所以只有后面的数不用动，所以队尾都不是逆序。所以我们计算一下末尾的那几个数的长度，这就是有多少个不用操作的数，这样第一问的$K$就解决了。

我们用树状数组维护目前出现过的元素。

我们用update函数标记这个区间$p_i$ 这个地方。

我们可以然后从1到k循环，得到答案，求完答案再update一下就做完了。

具体可以看注释

#include <bits/stdc++.h>

using namespace std;


const int MAXN = 500005;

int n;

int c[MAXN], a[MAXN];

inline int lowbit(int x) { return x & -x; }//lowbit

void update(int x) {//标记函数
    while (x <= n) {
        c[x]++;
        x += lowbit(x);
    }
}

int sum(int x) {//求和函数
    int res = 0;
    while (x > 0) {
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    int k = n - 1;
    while (k > 0 && a[k] < a[k + 1]) { //求k
        k--;
    }
    printf("%d\n", k); //先输出k
    for (int i = k + 1; i <= n; ++i) { //一开始标记不需要动的
        update(a[i]);
    }
    for (int i = 1; i <= k; ++i) { //求需要动的答案
        printf("%d ", k - i + sum(a[i]));
        update(a[i]);
    }
    printf("\n");
    return 0;
}

看蒟蒻写的这么认真，点个赞再走呗~