P6278 [USACO20OPEN]Haircut G题解

ghostdoglzd · 2020-10-15 20:01:27 · 题解

原题

题意概括：

• 有长为n的序列 a[1...n],\forall a[i](0<i\le n),a[i]\le n。
• 请你按 j(j=0,1,2,...,n-1) 依次输出把大于 j 的 a[i] 变为 j 后逆序对的个数。

思路：

这是一道很好的思考题，我们可以把 a[1..n] 按从小到大的顺序排序，对于每个 a[i]，在原序列中它前面比它大的数的个数即为其对 j=a[i]+1,a[i]+2,...,n 时的答案的贡献。然后从 0 到 (n-1) 枚举 j。每次枚举先输出答案，再把答案加上等于 j 的 a[i] 的贡献即可。

这个贡献可以利用树状数组维护区间和把复杂度降为 O(\log n) 。具体实现方式为先往树状数组的每一位上放1。然后每遍历到一个 a[i],将它在原序列中的位置对应的树状数组值改为 0，其贡献即为它在原序列中的位置前还有多少 1，即 query(num[i]-1),（num[i] 为 a[i] 在原序列中的位置）。

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
inline int rread(){
    int x=0;
    char c=getchar(),o=' ';
    while(c<'0'||c>'9')o=c,c=getchar();
    while(c>='0'&&c<='9')x*=10,x+=(c^48),c=getchar();
    if(o=='-')x=-x;
    return x;
}
inline int lowbit(int x){
    return x&(-x);
}
struct node{
    int a,num;
}nd[100010];
bool operator <(const node& x,const node& y){
    return (x.a==y.a)?x.num<y.num:x.a<y.a;
}
int n,tree[100010];
inline void change(int x,int c){
    while(x<=n){
        tree[x]+=c;
        x+=lowbit(x);
    }
}
inline int query(int x){
    int ans=0;
    while(x>0){
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
signed main(){
    n=rread();
    for(int i=1;i<=n;i++){
        nd[i].a=rread();
        nd[i].num=i;
        change(nd[i].num,1);
    }
    sort(nd+1,nd+1+n);
    int ans=0;
    int in=1;
    for(int i=0;i<n;i++){
        cout<<ans<<'\n';
        int t=in;
        while(i==nd[t].a){
            ans+=query(nd[t].num-1);
            change(nd[t].num,-1);
            t++;
        }
        in=t;
    }
    return 0;
}

更新日志

2020.10.16 修改了链接