逆序对

1688 求逆序对

题目描述 Description

给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目

数据范围：N<=10⁵。Ai<=10⁵。时间限制为1s。

输入描述 Input Description

第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。

输出描述 Output Description

所有逆序对总数.

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

 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     if(s==t)return;
12     int mid=(s+t)/2;
13     f(s,mid);
14     f(mid+1,t);//递归调用 
15     long long int i=s;
16     long long int j=mid+1;
17     now=s;
18     while(i<=mid&&j<=t)
19     {
20         if(a[i]<=a[j])//前半段小于后半段 
21             ans[now++]=a[i++];//ans数组用于存储当前答案 
22         else
23         {  
24             tot+=mid-i+1;//后半段大，将前段剩余部分加入答案 
25             ans[now++]=a[j++];//将后半段存入 
26         }
27     }
28     while(i<=mid)//此while&&下while将多出的部分存入ans 
29         ans[now++]=a[i++];
30     while(j<=t)
31         ans[now++]=a[j++];
32     for (i=s;i<=t;i++)//将ans存入a 
33         a[i] = ans[i];
34 }
35 int main()
36 {
37     long long int n;
38     cin>>n;
39     for(int i=1;i<=n;i++)
40         cin>>a[i];
41     f(1,n);
42     cout<<tot;
43     return 0;
44 }

逆序对

测试通过 Accepted