题解 P6278 【[USACO20OPEN]Haircut G】

· · 题解

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

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

看到对于每一个 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组，下赛季加油咯