P1908 逆序对 树状数组

概述    #include<bits/stdc++.h>using namespace std; const int maxn=5e5+10; #define ll long longint a[maxn],b[maxn]; ll c[maxn]; int n; ll ask(int x) { ll ans=0; for(; x; x-=x&-x) ans+=c[x]; return ans

 

 

#include<bits/stdc++.h>using namespace std; const int maxn=5e5+10; #define ll long longint a[maxn],b[maxn]; ll c[maxn]; int n; ll ask(int x) { ll ans=0; for(; x; x-=x&-x) ans+=c[x]; return ans; } voID add(int x,int y) { for(; x<=n; x+=x&-x) c[x]+=y; } int main() { scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%d",&a[i]); b[i]=a[i]; } sort(b+1,b+1+n); int cnt=unique(b+1,b+1+n)-b-1; ll ans=0; for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+cnt,a[i])-b; for(int i=n; i>=1; i--) { ans=ans+ask(a[i]-1); add(a[i],1); } printf("%lld",ans); }

总结

以上是内存溢出为你收集整理的P1908 逆序对 树状数组全部内容，希望文章能够帮你解决P1908 逆序对 树状数组所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。