题目描述
离散化+树状数组
可以作为一个板子记下来?
样例
#include<iostream>
#include<algorithm>
using namespace std;
#define lowbit(x) ((x)&-(x))
const int N=1e5+2;
struct pi{ int num,val;
}q[N];
bool cmp(pi x,pi y){
if(x.val==y.val) return x.num<y.num;
return x.val<y.val;
}
int n;
int tree[N];
int rk[N];
long long ans;
void update(int x,int d){
while(x<=N){
tree[x]+=d;
x+=lowbit(x);
}
}
int sum(int x){
int ans=0;
while(x>0){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&q[i].val),q[i].num=i;
sort(q+1,q+n+1,cmp);
for(int i=1;i<=n;++i) rk[q[i].num]=i;
for(int i=n;i>=1;--i) {
update(rk[i],1);
ans+=sum(rk[i]-1);
}
printf("%lld ",ans);
return 0;
}