1688 求逆序对

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 long long int a[1000001];
 5 long long int tot;
 6 long long int n;
 7 long long int ans[1000001];//储存结果 
 8 long long int now;//表示已经有多少个结果 
 9 void f(long long int s,long long int t)
10 {
11     //int mid,i,j,k;
12     if(s==t)return;
13     int mid=(s+t)/2;
14     f(s,mid);
15     f(mid+1,t);
16     long long int i=s;
17     long long int j=mid+1;
18     now=s;
19     while(i<=mid&&j<=t)
20     {
21         if(a[i]<=a[j])
22         {
23             //tot++;
24         
25             ans[now]=a[i];
26             i++;
27             now++;
28         }
29         else
30         {    
31             tot=tot+mid-i+1;
32             ans[now]=a[j];
33             j++;
34             now++;
35         }
36     }
37     while(i<=mid)
38     {
39         ans[now]=a[i];
40         i++;
41         now++;
42     }
43     while(j<=t)
44     {
45         ans[now]=a[j];
46         j++;
47         now++;
48     }
49     for (i=s;i<=t;i++)//把合并后的有序数据重新放回a数组
50         a[i] = ans[i];
51 
52 }
53 int main()
54 {
55     long long int n;
56     cin>>n;
57     for(int i=1;i<=n;i++)
58         cin>>a[i];
59     f(1,n);
60     cout<<tot;
61     /*for(int i=1;i<=n;i++)
62     {
63         cout<<a[i]<<" ";
64     }*/
65     return 0;
66 }