| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
The problem is the following:
We have array $$$a$$$ of $$$n$$$ integers and for each integer $$$k$$$ from $$$1$$$ to $$$n$$$ we want to calculate the number of pairs $$$(i, j)$$$ such that $$$a_i + a_j = k$$$.
I wonder if it can be solved in less than $$$\mathcal{O}(n^2)$$$
UPD: turns out it is a classical FFT problem
Lets transform the formula: We need to counting such pair $$$(i, j)$$$ satisfy $$$(k - a_i = a_j)$$$
So for each element $$$a[i]$$$ from $$$i = 1 \rightarrow n$$$
Lets $$$f(x) = $$$ number of appearance of $$$x$$$ in $$$a[1..i-1]$$$
Then we have the number of pair $$$(j < i)$$$ satisfy the formula is $$$f(k - a[i])$$$
Then the result will be $$$res = \underset{i = 1}{\overset{n}{\Sigma}} f(k - a[i])$$$
By storing the number of appearance in a tree ($$$map<>$$$), the complexity is $$$O(n\ log\ n)$$$
If the value is small we can use a frequency array to archive $$$O(n + max(ai))$$$ solution
Else by using hash table, you dont need that $$$O(log\ n)$$$ factor for finding such number in tree. Hence we archive $$$O(n)$$$ solution
Using the above idea. We have to calculate
Lets $$$g(k) = \underset{i = 1}{\overset{n}{\Sigma}} f(k - a[i])$$$
Lets $$$cost[k]$$$ is the value $$$g(k + 1) - g(k)$$$ so that we have $$$g(k + 1) = g(k) + cost[k]$$$
Then for each $$$a[i]$$$ ($$$i = 1 \dots n$$$)
We have to increase all $$$cost[j]$$$ ($$$j = 1 \dots n-1$$$) by $$$f(j - a_i + 1) - f(j - a_i)$$$
We can do that by some data structures that reduce the complexity down to $$$O(polylog\ n)$$$
Then for each queries $$$k = 1 \dots n$$$
The result will be $$$g(k)$$$
And by the transistion $$$g(k) = g(k - 1) + cost[k - 1]$$$ we can calculate next query in $$$O(1)$$$