圣堂之地 @ 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] 的区间和。