Loserinlife's blog

By Loserinlife, history, 8 months ago,

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!

• +3

 » 8 months ago, # |   +6 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. for full(B)<->partial(A) and full(B)<->full(A), we use the result of precalculation. for partial(B)<->full(A), we use the result of precalculation, too. for 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)$
 » 8 months ago, # | ← Rev. 2 →   0 two times offline 4D Mo algoO(n^1.75)
•  » » 8 months ago, # ^ |   0 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.