P5200 [USACO19JAN]Sleepy Cow Sorting（树状数组，模拟）

· · 题解

P5200 Sleepy Cow Sorting

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

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

又因为每头牛最多被移动一次（显然每次只能移动队头，最多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;
}

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