求冒泡的次数 (树状数组)-白红宇

求冒泡的次数 (树状数组)

阅读量：6839 次

发布时间：2019-06-26

本文共 2844 字，大约阅读时间需要 9 分钟。

BIT+离散化

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 int n,a[500010]; 6 int num[500010]; 7 long long ans; 8 struct node{ 9   int id,w;10 }q[500010];11 int cmp(node a,node b)12 {13     return a.w
         
          =1){21         cnt+=num[i];i-=lowbit(i);22     }23     return cnt;24 }25 void update(int i,int val){26     while(i<=n){27         num[i]+=val;i+=lowbit(i);28     }29 }30 int main()31 {32     int i,j,k;33     while(scanf("%d",&n)!=EOF){34         if(n==0) break;35         memset(num,0,sizeof(num));36         ans=0;37         for(i=1;i<=n;i++){38           q[i].id=i;39           scanf("%d",&q[i].w);40         }41         sort(q+1,q+n+1,cmp);42         for(i=1;i<=n;i++) a[q[i].id]=i;43         for(j=1;j<=n;j++)44         {45             update(a[j],1);46             ans+=j-sum(a[j]);47         }48         printf("%lld\n",ans);49     }50     return 0;51 }

View Code

1 #include 
      
        2 #include 
        3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 using namespace std;13 #define INF 0x3f3f3f3f14 #define MAX 10001015 16 typedef long long ll;17 int n,a[MAX],bit[MAX];18 19 int sum(int i)20 {21 int s=0;22 while(i>0){23 s+=bit[i];24 i -= i&-i;25 }26 return s;27 }28 29 void add(int i,int x)30 {31 while(i<=n){32 bit[i]+=x;33 i += i&-i;34 }35 }36 37 void solve()38 {39 int ans=0;40 for(int j=1; j<=n; j++){41 add(a[j],1);42 ans += j-sum(a[j]); 43 }44 printf("%d\n",ans);45 }46 47 int main()48 {49 int t;50 scanf("%d",&t);51 while(t--){52 memset(a,0,sizeof(a));53 memset(bit,0,sizeof(bit));54 scanf("%d",&n);55 for(int i=1; i<=n; i++){56 scanf("%d",&a[i]);57 }58 solve();59 }60 }

View Code

归并:

1 #include 
     
       2  3 const int N=500000+10; 4  5 int n,a[N],temp[N]; 6 long long ans; 7  8 void merge_sort(int l,int r) 9 {10     if (r-l<=1) return;11     int m=(l+r)>>1;12     int p=l,q=m,i=l;13     merge_sort(l,m);14     merge_sort(m,r);15     while (p
      
       =r || (p

1 #include 
      
        2 #include 
        3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 using namespace std;13 #define INF 0x3f3f3f3f14 #define MAX 10001015 16 const int N=500000+10;17 18 int n,a[N],temp[N];19 long long ans;20 21 void merge_sort(int l,int r)22 {23 if (r-l<=1) return;24 int m=(l+r)>>1;25 int p=l,q=m,i=l;26 merge_sort(l,m);27 merge_sort(m,r);28 while (p
                 
                  =r || (p