hdu 5517 Triple(二维树状数组)

Problem Description
Given the finite multi-set A of n pairs of integers, an another finite multi-set B of m triples of integers, we define the product of A and B as a multi-set

C=AB={a,c,da,bA, c,d,eB and b=e}

For each a,b,cC, its BETTER set is defined as

BETTERC(a,b,c)={u,v,wCu,v,wa,b,c, ua, vb, wc}

As a \textbf{multi-set} of triples, we define the TOP subset (as a multi-set as well) of C, denoted by TOP(C), as

TOP(C)={a,b,cCBETTERC(a,b,c)=}

You need to compute the size of TOP(C).

 

Input
The input contains several test cases. The first line of the input is a single integer t (1t10) which is the number of test case. Then t test cases follow.

Each test case contains three lines. The first line contains two integers n (1n105) and m (1m105) corresponding to the size of A and B respectively.
The second line contains 2×n nonnegative integers

a1,b1,a2,b2,,an,bn

which describe the multi-set A, where 1ai,bi105.
The third line contains 3×m nonnegative integers

c1,d1,e1,c2,d2,e3,,cm,dm,em

corresponding to the m triples of integers in B, where 1ci,di103 and 1ei105.

 

Output
For each test case, you should output the size of set TOP(C).

 

Sample Input
2 5 9 1 1 2 2 3 3 3 3 4 2 1 4 1 2 2 1 4 1 1 1 3 2 3 2 2 4 1 2 2 4 3 3 2 3 4 1 3 3 4 2 7 2 7 2 7 1 4 7 2 3 7 3 2 7 4 1 7

 

Sample Output
Case #1: 5 Case #2: 12
题意有太多公式就不想说了。。。
如果一个个枚举的话太大了,但是发现对于二元组来说,如果相同的b我们只用保留最大的a即可。那么暴力合并二元组和三元组即可,这个过程完成后需要去重并且计数,去重的细节较多(在这里狗带了两个小时)。。。然后剩下的排序a一维然后注意到c,d很小二维树状数组暴力统计即可。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注