思维题，挺不错的一个树状数组题，代码不长，甚至不需要排序

考场上一看到这题其实窝是懵的，接下来，输出的方式给了我一点提示

看到对于每一个 j=0,1,…,N−1，用一行输出 Farmer John 头发的不良度我们想到了倒推

如何倒推呢？我们考虑FJ去种头发而不是剃头发（大雾）

为了便于理解，我们强行加一个时间，我们假设每一秒fj的头发都会长1微米，然后第 $i$ 个头发在长度到达 $A_i$ 的时候就不会继续长了

于是，我们考虑每一秒新增的逆序对数

发现第 $i$ 秒新增的逆序对数就是每个长度为 $i-1$ 的头发的前面在第 $i-1$ 秒时还在长的头发数量

发现，这句话我们换一种方式说就是第 $i$ 个头发对答案的贡献从第 $A_i$ 秒开始，并且贡献的大小为满足 $A_j>A_i(j<i)$ 的 $j$ 的个数

发现这东西就是个逆序对，树状数组维护一下就好啦~

code:

#include<bits/stdc++.h>
#define MAXN 100100
#define int long long//别忘记longlong哦
using namespace std;
int n,a[MAXN];
class tarray
{
private:
	int tree[MAXN];
	int lowbit(int x){return x&(-x);}
public:
	void update(int x,int y){while(x<=n){tree[x]+=y;x+=lowbit(x);}}
	int query(int x){int ret=0;while(x){ret+=tree[x];x-=lowbit(x);}return ret;}
}t;//树状数组
int s[MAXN],ans;
signed main()
{
	freopen("haircut.in","r",stdin);
	freopen("haircut.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]++;
	for(int i=1;i<=n;i++)//统计逆序对
	{
		int x=n-a[i]+2;
		s[a[i]]+=t.query(x-1);
		t.update(x,1);
	}
	printf("0");//第0秒的答案
	for(int i=2;i<=n;i++)//统计答案
	{
		ans+=s[i-1];
		printf("\n%lld",ans);
	}
	return 0;
}

后记：这个赛季usaco就卡在G组了，没能晋级P组，下赛季加油咯