Queries for counting pairs that sum to a given target

Revision en1, by not_wiz, 2023-09-07 08:54:18

We have an array of N integers and Q queries. In each query, we are given an integer X. For each query, we have to output the number of unordered pairs in array that sum to X.

How can we efficiently answer these sort of queries?

Constraints:

1 <= N <= 2 * 105

1 <= Q <= 2 * 105

1 <= |ai| <= 1018

1 <= X <= 1018

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English not_wiz 2023-09-07 08:54:18 478 Initial revision (published)