I_am_Invincible's blog

A query problem
By I_am_Invincible, 12 months ago, In English

You are given an array of size n. And given Q queries. In each query you will be given a number x. You need to find |a1-x| + |a2-x| + ..... Constraints are : 1<=n,Q<=1e5. Is it possible to solve this in O(n+Q) or within time timelimits?

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

»
12 months ago, hide # |
← Rev. 4  
Vote: I like it 0 Vote: I do not like it

If you know count (denote this cnt_le[x]) and sum (sum_le[x]) of all a[i]: a[i] <= x

and you know count (cnt_ge[x]) and sum (sum_ge[x]) of all a[i]: a[i] >= x

that you can calculate ans easily:

ans = (cnt_le[x] * x - sum_le[x]) + (sum_ge[x] - cnt_ge[x] * x)

You should fill these arrays only for a[i]: 1 <= a[i] <= 1e5. Just find the number of values for each value, and then use idea of prefix sums. It is O(n + 1e5) ~ O(n)

For other a[i] you can find sum and count separately, in O(n)

So after precalc in O(n) you can find answer in O(1) for each query.

Total: O(n + Q)

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

    Amazing.

    But how will you do if $$$\left(\min_{1\le i\le n}{a_i}\right)\gt10^5$$$?

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

      It is not a problem. "find sum and count separately" — I wrote. So denote

      cnt_big = count of all a[i]: a[i] > 1e5, sum_big = sum...

      Similarly, cnt_small and sum_small.

      Than the final formula:

      ans = ((cnt_le[x] + cnt_small) * x - (sum_le[x] + sum_small)) + ((sum_ge[x] + sum_big) - (cnt_ge[x] + cnt_big) * x)

      → Reply
  • »
    »
    12 months ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it 0 Vote: I do not like it

    There is other (maybe simpler) solution. This (and the previous one) the solution only works for 1 <= x <= 1e5.

    Denote cnt[y] = count of y in array. All a[i]: a[i] < 1 or a[i] > 1e5 you should skip.

    Let ans[x] is answer for query with x

    Just use brute force for calculate ans[1], also you need calculate prev = count of a[i]: a[i] <= 1. It is O(n)

    Then, if you have ans[1], you can simply calculate ans[2]:

    ans[2] = ans[1] + prev - (n - prev)

    Note, that if you add cnt[2] to pref, you can calculate ans[3]:

    ans[3] = ans[2] + prev - (n - prev)

    So you can calculate all ans[x]. Just

    for (int i = 2; i <= MX; i++) {
    ans[i] = ans[i - 1] + prev - (n - prev);
    prev += cnt[i];
}
    Code (C++)
    → Reply
»
12 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

It can be done easily by using two pointers.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Sort the queries with bucket sorting: xi<=xj(i<j). O(n+q) solve all queries. Sort again to print the answer.

→ Reply