xiaobei10 @ 2024-08-04 10:44:56
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int n,a[N],b[N],c[N];
long long t[N];
int lowbit(int x){
return x&(-x);
}
void modify(int x,int y){
for(int i=x;i<=n;i+=lowbit(i)){
t[i]+=y;
}
}
long long query(int x) {
long long res=0;
for(int i=x;i>0;i=i-lowbit(i)){
res+=t[i];
}
return res;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)b[i]=a[i];
sort(a+1,a+n+1);
int cnt=unique(a+1,a+n+1)-a-1;
for (int i = 1; i <= n; i++) {
a[i] = lower_bound(a + 1, a + cnt + 1, b[i]) - a;
}
long long ans=0;
for(int i=1;i<=n;i++){
ans=ans+query(cnt)-query(a[i]);
modify(a[i],i);
}
cout<<ans<<"\n";
return 0;
}by Kete @ 2024-08-14 11:51:03
不用那么麻烦，用
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define w while
using namespace std;
int a[500000+101],b[500000+101],n;
long long ans=0;
void gb(int l,int r) {
if(l==r)return ;
int mid=(l+r)/2;
gb(l,mid);
gb(mid+1,r);
int i=l,j=mid+1,k=l;
w(i<=mid&&j<=r) {
if(a[i]<=a[j])b[k++]=a[i++];
else {
b[k++]=a[j++];
ans+=(long long)mid-i+1;
}
}
w(i<=mid)b[k++]=a[i++];
w(j<=r)b[k++]=a[j++];
rep(i,l,r)a[i]=b[i];
}
int main() {
cin>>n;
rep(i,1,n)cin>>a[i];
gb(1,n);
cout<<ans;
return 0;
}