传送门
Solution:
由于数字的大小可能非常大，而且都是未知的，所以只能采用离散化的方式先将数组离散化。
每次把这个数的位置加入到树状数组中，因为是排完序之后，所以之前加入的一定比后加入的大
然后再查询当前这个数前面位置的数。
#include<bits/stdc++.h> #define N 40005 using namespace std; int n,ans,tree[N]; struct node { int val,num; }a[N]; inline bool cmp(const node &a,const node &b) { return a.val>b.val; } inline int lowbit(int x) { return x&-x; } inline void update(int x,int delta) { for(int i=x;i<=n;i+=lowbit(i)) tree[i]+=delta; } inline int query(int x) { int sum=0; for(int i=x;i>0;i-=lowbit(i)) sum+=tree[i]; return sum; } int main() { cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].val; a[i].num=i; } sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) { update(a[i].num,1); ans+=query(a[i].num-1); } cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9420179.html
