dernier_jour's blog

how to approach this problem
By dernier_jour, history, 18 months ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
18 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I suggest you actually mean the following?

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

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

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

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

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

→ Reply