树状数组求逆序对

P1908 逆序对

树状数组求逆序对

 

 树状数组求逆序对

 

 离散化+树状数组:AC_Code

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn=500010;
 5 
 6 int a[maxn],tree[maxn<<2],b[maxn];
 7 int cnt;
 8 
 9 int lowbit(int i){
10     return i&(-i);
11 }
12 
13 void updata(int i,int k){
14     while( i<=cnt ){
15         tree[i]+=k;
16         i+=lowbit(i);
17     }
18 }
19 
20 ll getsum(int i){
21     ll res=0;
22     while( i>0 ){
23         res+=tree[i];
24         i-=lowbit(i);
25     }
26     return res;
27 }
28 
29 int main()
30 {
31     int n;
32     scanf("%d",&n);
33     for(int i=1;i<=n;i++){
34         scanf("%d",&a[i]);
35         b[i-1]=a[i];
36     }
37     sort(b,b+n);
38     int reu=unique(b,b+n)-b;
39     cnt=reu;
40     memset(tree,0,sizeof(tree));
41     ll ans=0;
42     for(int i=1;i<=n;i++){
43         int f=lower_bound(b,b+reu,a[i])-b+1;
44         ll t=getsum(cnt)-getsum(f);        //t=getsum(cnt)-getsum(a[i]);
45         updata(f,1);
46         ans += t;
47     }
48     cout<<ans<<endl;
49     return 0;
50 }    

 

原文链接: https://www.cnblogs.com/wsy107316/p/12288467.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬

    树状数组求逆序对

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/328253

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年3月1日 下午4:37
下一篇 2023年3月1日 下午4:37

相关推荐