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

Автор dernier_jour, история, 18 месяцев назад, По-английски

given an array $$$a$$$ of length $$$n$$$, you have to answer $$$m$$$ queries:

  • decrease the numbers greater than $$$x$$$ by $$$x$$$ in the interval $$$[l,r]$$$
  • count the occurrence of $$$x$$$ in the interval $$$[l, r]$$$

i have no progress so far.

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

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

I suggest you actually mean the following?

Operation 1: decrease the numbers greater than $$$x$$$ by $$$x$$$ in the interval $$$[l,r]$$$

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

You should frame the question better, 1.are the changes permanent,2.is x constant throughout the queries?

»
18 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

i think you can use sqrt decomposition to solve in $$$\mathcal{O}(n \sqrt{n} \log{n})$$$

basically, turn the array into blocks of size $$$\sqrt{n}$$$. in each block, store a map for $$$(\text{val}, \text{freq})$$$

updates: for each block, either lazily add +x to the entire block, or update specific elements.

queries: just iterate thru each block and add relevant values. we can handle stuff that isn't in a complete block separately