Given an array of n integers and q queries. Each query consists of 4 integers (x, y, u, v) (1 <= x <= y <= n, 1 <= u <= v <= n)

Find the sum of abs(a[i] — a[j]) for all pairs (i, j) where x <= i <= y, for all u <= j <= v

N, Q <= 1e5

Ai <= 1e9

Thanks!

I have a approach that is a bit complex, and I'm not sure if it's correct.

Square root decomposition. Precalculate

`ptob[i][j]`

, meaning $$$\sum\limits_{k \in \text{block}_j} |a_k - a_i|$$$. And we will use its 2D prefix sum. Here is $$$O(n\sqrt{n})$$$.For each query, we have two ranges: A and B, and we have some full blocks and partial blocks.

`full(B)<->partial(A)`

and`full(B)<->full(A)`

, we use the result of precalculation.`partial(B)<->full(A)`

, we use the result of precalculation, too.`partial(A)<->partial(B)`

, it requires something else...Consider two arrays $$$\{a\}$$$ and $$$\{b\}$$$, in order to calculate $$$\sum_{i, j} |a_i - b_j|$$$ faster than brute force, we sort both array and do something similar to merge sort. It needs we to prepare sorted result of every blocks. When queried, just filter out all the numbers we need. Additionally, it works when both A and B didn't include any full blocks.

Total time complexity is $$$O((n+q)\sqrt n)$$$

two times offline 4D Mo algo

O(n^1.75)

Could you pls tell me some details about this? I feel confused because I have no idea how to calculate the contribution of a new single element to be included rapidly.