Loserinlife's blog

Square root decomposition problem?
By Loserinlife, history, 10 months ago, In English

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!

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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)$$$

→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

two times offline 4D Mo algo

O(n^1.75)

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply