Lookup cost in a chained table

Scenario

Kestrel Stream keeps track ids in a hash table with separate chaining. A track goes to bucket id mod buckets. Each bucket keeps its tracks in a chain, in the order the tracks were first stored, and a track that is already stored is not stored again.

To find a track, the table walks the chain of its bucket from the front and compares ids one at a time. Finding a stored track takes as many comparisons as its position in the chain, counting from 1. A track that is not stored takes one comparison for every track in the chain.

Your task

Write lookup_cost(keys, queries, buckets).

keys[i] is the i-th track id stored. A repeated id is ignored, and the first occurrence decides the order in its chain.
queries[j] is a track id that is searched for after all keys are stored. A query may or may not be stored.
A stored query costs its 1-based position in its chain. An id that is not stored costs the length of its bucket's chain, which may be 0.
Return the total cost of all queries.

Examples

Example 1 (traced)#

text2 lines

Input:  keys = [14, 9, 21, 14, 4, 19, 6], queries = [4, 19, 8, 6, 3], buckets = 5
Output: 9

Distinct keys in order are 14, 9, 21, 4, 19 and 6. With 5 buckets, 14, 9, 4 and 19 go to bucket 4, 21 and 6 go to bucket 1. The chains are bucket 4: 14, 9, 4, 19 and bucket 1: 21, 6.

Query	Bucket	Stored	Cost
4	4	yes, position 3	3
19	4	yes, position 4	4
8	3	no, empty chain	0
6	1	yes, position 2	2
3	3	no, empty chain	0

The total is 3 + 4 + 0 + 2 + 0 = 9.

Example 2#

text2 lines

Input:  keys = [1, 2, 3], queries = [9, 9], buckets = 1
Output: 6

One chain holds 1, 2 and 3. The id 9 is not stored, so each search walks all 3 tracks. The total is 3 + 3 = 6.

Example 3#

text2 lines

Input:  keys = [7, 7, 7], queries = [7], buckets = 4
Output: 1

Only one copy of 7 is stored, so it is at position 1.

Constraints

1 ≤ keys.length ≤ 100,000 (tracks stored)
1 ≤ queries.length ≤ 100,000 (lookups)
1 ≤ keys[i], queries[j] ≤ 10^6 (track ids)
1 ≤ buckets ≤ 100,000

What does n, q ≤ 10^5 tell you?

Building each query's chain by scanning all the keys costs q × n checks, which is 10^10 at the largest size, with a chain scan for each key. That is far over the budget of about 10^8 simple operations a second. Storing each key's chain position once makes the pass about n steps, and each query then costs one map lookup.

Read the values too. One query can cost up to 10^5 comparisons, and 10^5 queries can add up to 10^10. That is beyond a 32-bit integer, so use a 64-bit type for the total.

Scenario

Your task

Write lookup_cost(keys, queries, buckets).

keys[i] is the i-th track id stored. A repeated id is ignored, and the first occurrence decides the order in its chain.
queries[j] is a track id that is searched for after all keys are stored. A query may or may not be stored.
A stored query costs its 1-based position in its chain. An id that is not stored costs the length of its bucket's chain, which may be 0.
Return the total cost of all queries.

Examples

Example 1 (traced)#

text2 lines

Input:  keys = [14, 9, 21, 14, 4, 19, 6], queries = [4, 19, 8, 6, 3], buckets = 5
Output: 9

Distinct keys in order are 14, 9, 21, 4, 19 and 6. With 5 buckets, 14, 9, 4 and 19 go to bucket 4, 21 and 6 go to bucket 1. The chains are bucket 4: 14, 9, 4, 19 and bucket 1: 21, 6.

Query	Bucket	Stored	Cost
4	4	yes, position 3	3
19	4	yes, position 4	4
8	3	no, empty chain	0
6	1	yes, position 2	2
3	3	no, empty chain	0

The total is 3 + 4 + 0 + 2 + 0 = 9.

Example 2#

text2 lines

Input:  keys = [1, 2, 3], queries = [9, 9], buckets = 1
Output: 6

One chain holds 1, 2 and 3. The id 9 is not stored, so each search walks all 3 tracks. The total is 3 + 3 = 6.

Example 3#

text2 lines

Input:  keys = [7, 7, 7], queries = [7], buckets = 4
Output: 1

Only one copy of 7 is stored, so it is at position 1.

Constraints

1 ≤ keys.length ≤ 100,000 (tracks stored)
1 ≤ queries.length ≤ 100,000 (lookups)
1 ≤ keys[i], queries[j] ≤ 10^6 (track ids)
1 ≤ buckets ≤ 100,000

What does n, q ≤ 10^5 tell you?

Read the values too. One query can cost up to 10^5 comparisons, and 10^5 queries can add up to 10^10. That is beyond a 32-bit integer, so use a 64-bit type for the total.