The third problem:

Let’s notice that all elements are unique, what it gives us

### Subproblem 1:

K is fixed, the answer is no more than N, we can store the values = 1 in the points (X, Y), where |p[x] - p[y]| = K. Do you see how to do updates and queries in quick O(log^2) time?

Consider the summation on sub-matrix [L..R, L..R]

### Subproblem 2:

Imagine we solve the problem without updates, then if we somehow know all the elements in the range l..r then we can find the answer by (set \& (set < < k)).count() if you’re familiar with C++ bitset. We can find the set with the Mo’s algorithm, don’t forget that there is boosted Mo’s algorithm with Hilbert order.

And updates can be handled with Mo’s algorithm with updates:

So, the total complexity is O(Q (N^(2/3) + N/64)), I haven’t seen such complexities before

Feel free to ask questions, I can add links to the algorithms I mentioned. Also, to explain the things more clearly.