kanchui666 @ 2022-08-10 18:39:59
#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int n,ans;
int a[N],b[N],t[N];
int lowbit(int x){
return x&(-x);
}
void add(int x,int y){
for(int i=x;i<=n;i+=lowbit(i))
{
t[i]+=y;
}
}
int query(int x){
int anss=0;
for(int i=x;i;i-=lowbit(i))
{
anss+=t[i];
}
return anss;
}
int cmp(int x,int y){
return a[x]<a[y];
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=i;
}
stable_sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;i++)
{
a[b[i]]=i;
}
for(int i=1;i<=n;i++)
{
add(a[i],1);
ans+=(i-query(a[i]));
}
printf("%d",ans);
return 0;
}
by Eason2009 @ 2022-08-10 18:44:12
开long long,还有你这个离散化遇到重复数字就会炸啊
by irris @ 2022-08-10 18:53:07
你离散化了个你好寂寞
by 老_王 @ 2022-08-10 19:06:26
这不归并排序板子吗
by C201529 @ 2022-08-10 19:49:54
把