not_wiz's blog

Queries for counting pairs that sum to a given target
By not_wiz, history, 9 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

»
9 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
  • »
    »
    9 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Got it. Thanks

    Also, I would need to cube the polynomial or raise to some appropriate sufficient power in case if k is greater than 2*m in order to obtain the term xk, right?

    → Reply