not_wiz's blog

Queries for counting pairs that sum to a given target
By not_wiz, history, 14 months ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
14 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Well this can't be done faster than $$$O(n*q)$$$ if you keep the constraints, however if you let $$$a[i] \leq 2*10^5$$$, then you've got yourself an FFT task. Consider a polynomial $$$cnt[1]*x^1+cnt[2]*x^2 +$$$ $$$...$$$ $$$+ cnt[m]*x^m$$$, if you square it you can get the number of pairs which add up to $$$k$$$ by taking the coefficient of $$$x^k$$$. Try to see why multiplying polymomials works by doing it for small $$$n$$$ on paper

→ Reply