shivam_360's blog

Can anyone suggest possible approaches?
By shivam_360, history, 15 months ago, In English

we are given with an array of n integers n<=10^5 , we need to answer q queries q<=10^5 , in each query we are given with l,r and an integer x, for each query we need to answer the summation of |a[i]-x| for all i>=l && i<=r (summation of absolute difference of each number with x in range l and r)..as constraints are big we need to solve each query in less than n... Can anyone suggest some approach with some thought process....

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

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Prefix arrays would help.

→ Reply
»
15 months ago, # |
← Rev. 7   Vote: I like it +5 Vote: I do not like it

If we can answer the following questions quickly, we will succeed:

(1) How many numbers $$$n$$$ in $$$\{a[l], ..., a[r]\}$$$ are less or equal than $$$x$$$?

(2) What is the sum of numbers of $$$n$$$ such that $$$n \in \{a[l], ..., a[r]\}$$$ and $$$n \leq x$$$?

These two questions can be answered using a persistent segment tree, also known as the "主席树".

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    yay!! great approach.... Thanks for the idea man...

    → Reply