Hey, I've been trying to solve the following problem. Given an array of $$$n \leq 2*10^5$$$ distinct positive integers $$$a_1, a_2, \dots, a_n$$$ find the number of triplets ($$$i$$$, $$$j$$$, $$$k$$$) and $$$i < j < k$$$ such that $$$a_j - a_i = a_k - a_j$$$ (so $$$a_i$$$, $$$a_j$$$, $$$a_k$$$ form an arithmetic progression). Additionally, the test cases were made such that the answer is not greater than $$$10^6$$$.

I could only come up with a $$$O(n^2)$$$ solution and have no idea how to go further (maybe some FFT/Convolutions?). Any hints/help would be appreciated, thanks in advance!

Why would you need FFT/convolutions? An $$$O(nlogn)$$$ solution is easy to think of & implement.

Sort the array first. Then enumerate through all $$$j$$$ s. Therefore the formula is transformed into $$$2\times a_j=a_i+a_k$$$. The left part is determined; the right can be solved using binary search.

How would you solve it with binary search? Also, remember that the order of given integers matters (for $$$1$$$, $$$2$$$, $$$3$$$ answer is $$$1$$$ while for $$$2$$$, $$$3$$$, $$$1$$$ answer is $$$0$$$).

https://codeforces.com/problemset/problem/452/F

Hash + segment tree

But I guess this problem is different because array elements ai is not a permutation of numbers from 1 to n.

It's not the same problem as in my problem you need to find

numberof different triples, while in the problem you've posted you need to check whether thereexistsany triple.I'm sorry I can't help you.:(

When the sequence is arranged, the difficulty of determining the existence is * 2700, and the difficulty of counting may be greater than 3000

You can find this problem on CodeChef. https://www.codechef.com/problems/COUNTARI

Thanks, didn't know about this problem! The problem is that values in that problem are up to $$$3*10^4$$$ while mine can be up to $$$10^5$$$. Maybe it will fit TL, but I'm wondering whether there is any way to use the fact that answer is not greater than $$$10^6$$$.

Excuse me, but I think this is a variant of 3SUM? If this is true, then there would be no easy way to reduce it to under $$$O(n^2)$$$ time. Can we know the range of the array's elements? It may give a hint on whether FFT works or not.

Yes, the only way to do it in

O(nlogn)is using FFT, and that can be optimized a little more with blocks, like than we find the number of primes in the interval.The input array $$$a_1, a_2, a_3, \dots, a_n$$$ is a permutation of $$$1, 2, \dots, n$$$ so all elements are distinct and $$$1 \leq a_i \leq n$$$.

Now I am thinking if this problem may be some usage of prefix sum + suffix sum + DP, but I am not very sure on how. Can anyone help me on this approach?