R - Japan

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

Input

Output

For each test case write one line on the standard output: Test case (case number): (number of crossings)

Sample input and output

Sample Input	Sample Output
1 3 4 4 1 4 2 3 3 2 3 1	Test case 1: 5

Hint

The data used in this problem is unofficial data prepared by pfctgeorge. So any mistake here does not imply mistake in the offcial judge data.

思路：

又是逆序对，具体的不多说了，和前面的某题一样，，，

归并求逆序对数，，

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <queue>
 7 #include <stack>
 8 #include <map>
 9 #include <vector>
10 #include <cstdlib>
11 #include <string>
12 
13 #define PI acos((double)-1)
14 #define E exp(double(1))
15 using namespace std;
16 
17 vector<pair<long long,long long > >p;
18 long long  a[2000000+5];
19 long long  temp[2000000+5];
20 long long  cnt=0;//逆序对的个数
21 void merge(int left,int mid,int right)
22 {
23     int i=left,j=mid+1,k=0;
24     while (( i<=mid )&& (j<=right))
25         if (a[i]<=a[j]) temp[k++]=a[i++];
26         else
27         {
28             cnt+=mid+1-i;//关键步骤
29             temp[k++]=a[j++];
30         }
31     while (i<=mid) temp[k++]=a[i++];
32     while (j<=right) temp[k++]=a[j++];
33     for (i=0,k=left; k<=right;) a[k++]=temp[i++];
34 }
35 void mergeSort(int left,int right)
36 {
37     if (left<right)
38     {
39         int mid=(left+right)/2;
40         mergeSort(left, mid);
41         mergeSort(mid+1, right);
42         merge(left, mid, right);
43     }
44 }
45 int main (void)
46 {
47     int n,u,v,t;
48     cin>>t;
49     for(int i=1;i<=t;i++)
50     {
51         p.clear();
52         cnt=0;
53         cin>>u>>v>>n;
54         for(int i=0; i<n; i++)
55         {
56             long long k,b;
57             scanf("%lld%lld",&k,&b);
58             p.push_back(make_pair(k,b));
59         }
60         sort(p.begin(),p.end());
61         for(int i=0; i<n; i++)
62             a[i]=p[i].second;
63         mergeSort(0,n-1);
64         printf("Test case %d: %lld
",i,cnt);
65     }
66     return 0;
67 }

View Code