You are given two sequences a and b which may contain repeated numbers. A pair (i,j) is good when ai is picked from the first sequence and bj is picked from the second sequence and ai>bj.
You are asked to solve the number of good pairs of the two sequences.
The first line is an integer T which means the number of testcases. (T<=5)
The first line in each testcase is with two integers n and m. (0<n,m<=105)
The following n lines, each line with two integers x and y, means the amount of x in the first sequence is y.
The following m lines, each line with two integers x and y, means the amount of x in the second sequence is y.
(0<x<=109,0<y<=104)
For each testcase, print an integer meaning the number of good pairs
Sample Input
1 2 2 3 2 4 1 3 1 2 3
Sample Output
10
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 7 struct node 8 { 9 int v; 10 int n; 11 }; 12 13 bool operator<(const node &a, const node &b) 14 { 15 return a.v < b.v; 16 } 17 18 node A[100001], B[100001]; 19 int n,m; 20 int aa; 21 char buf[1<<15],*S=buf,*H=buf,ch; 22 char getc(){return S==H&&(H=(S=buf)+fread(buf,1,1<<15,stdin),S==H)?0:*S++;} 23 int F(){ 24 while(ch=getc(),ch<‘0‘||ch>‘9‘);aa=ch^‘0‘; 25 while(ch=getc()^‘0‘,ch>=0&&ch<=9)aa=(aa<<3)+(aa<<1)+ch;return aa; 26 } 27 28 unsigned long long dp[100001]; 29 30 31 unsigned long long goodPair() 32 { 33 dp[0] = B[0].n; 34 for (int j = 1; j < m; ++j) { 35 dp[j] = B[j].n + dp[j-1]; 36 } 37 38 unsigned long long sum = 0; 39 int i = 0, j = 0; 40 while (i < n && A[i].v <= B[0].v) { 41 ++i; 42 } 43 for (; i < n; ++i) { 44 while (j < m && B[j].v < A[i].v) { 45 j++; 46 } 47 48 sum += A[i].n * dp[j-1]; 49 } 50 51 return sum; 52 } 53 54 55 int main() 56 { 57 int T = F(); 58 while (T--) { 59 n = F(); 60 m = F(); 61 for (int i = 0; i < n; ++i) { 62 A[i] = (node) {F(),F()}; 63 } 64 for (int i = 0; i < m; ++i) { 65 B[i] = (node) {F(),F()}; 66 } 67 68 sort(A, A+n); 69 sort(B, B+m); 70 71 cout << goodPair() << endl; 72 } 73 }
原文：http://www.cnblogs.com/liew/p/4366519.html