求助大佬!!谢谢!

P1908 逆序对

圣堂之地 @ 2019-07-26 21:05:16

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll MAX=1e6+5;

struct node{
    ll num;//编号 
    ll v;//权值 
}f[MAX];

ll n;//n个数 
ll ans;//逆序对个数 
ll c[MAX];//树状数组 

int getsum(int i){
    int s=0;
    while(i) s+=c[i],i-=i&(-i);
    return s;
}//求和 

inline void updata(int i){ while(i<=n) c[i]++,i+=i&(-i);}//c[i]的改变值值为1

inline bool cmp(node x,node y){ return x.v>y.v;}

inline ll read(){
    int x=0,f=1; char c=getchar();
    while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+(c^48); c=getchar();}
    return x*f;
}

int main(){

    n=read();
    for(register ll i=1;i<=n;i++) f[i].v=read(),f[i].num=i;

    sort(1+f,1+n+f,cmp);//排序(按权值大-->小)

    for(register ll i=1;i<=n;i++){
        updata(f[i].num);
        ans+=getsum(f[i].num);//我的逆序对有哪些 
    }

    printf("%lld",ans);

    return 0;
}

by 圣堂之地 @ 2019-07-26 21:05:46

排序是为了让 1 100000 200000 变为 1 2 3,我用结构体记录了一开始的顺序(即编号),对于任意一个 i 而言,其初始编号为 f[i].num 。 我从大往小的看,只要出现一个数,其 a[该数编号] ++ ,表示出现过一次。对于 i 而言,逆序对为 a[1] 到 a[该数编号-1] 的区间和。


|