Inversions SGU

这个是逆序对的裸题哇

归并排序或者树状数组~

树状数组的话需要离散化一下···

emm确实很水很水很水···

归并排序：

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <iostream>
 5 
 6 using namespace std;
 7 const int maxn=65537+1000;
 8 int a[maxn];
 9 int n;
10 int t[maxn];
11 long long ans;
12 void merge(int L,int R,int *A,int *T){
13     int mid=L+(R-L)/2;
14     if(R-L==1)return ;
15     merge(L,mid,A,T);
16     merge(mid,R,A,T);
17     int i=L,j=mid;
18     int pos=L;
19     while(i<mid||j<R){
20         if((A[i]<=A[j]&&i<mid)||j>=R){
21             T[pos++]=A[i++];
22         }
23         else{
24             T[pos++]=A[j++];
25             ans+=mid-i;
26         }
27     }
28     for(i=L;i<R;i++)A[i]=T[i];
29 }
30 int main(){
31     ans=0;
32     scanf("%d",&n);
33     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
34     merge(1,n+1,a,t);
35     cout<<ans;
36    //for(int i=1;i<=n;i++)
37    // cout<<a[i]<<" ";
38 
39 return 0;
40 }

View Code

树状数组：

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 const int maxn=65537+10;
 8 int a[maxn];
 9 int m[maxn];
10 int n;
11 int C[maxn];
12 int lowbit(int x){
13     return x&(-x);
14 }
15 void add(int v,int x){//a[v]+=x
16     while(v<=n){
17         C[v]+=x;
18         v+=lowbit(v);
19     }
20 }
21 int query(int v){//sum[v]
22     int res=0;
23     while(v>=1){
24         res+=C[v];
25         v-=lowbit(v);
26     }
27     return res;
28 }
29 int Max=-1;
30 int main(){
31     scanf("%d",&n);
32     for(int i=1;i<=n;i++){scanf("%d",&a[i]);}
33     for(int i=1;i<=n;i++)m[i]=a[i];
34     sort(m+1,m+1+n);
35 
36     long long ans=0;
37     for(int i=1;i<=n;i++){
38         int num=lower_bound(m+1,m+1+n,a[i])-m;
39         add(num,1);
40         ans+=query(n)-query(num);
41     }
42     cout<<ans;
43 return 0;
44 }

View Code