Блог пользователя shivam_360

Can anyone suggest possible approaches?
Автор shivam_360, история, 22 месяца назад, По-английски

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....

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Prefix arrays would help.

→ Ответить
»
22 месяца назад, # |
← Rev. 7   Проголосовать: нравится +5 Проголосовать: не нравится

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 "主席树".

→ Ответить