Who knows which Chinese DS trivialises this standard array problem?

Revision en2, by NovusStellachan, 2024-05-29 19:27:21

Ok, here's the formal statement:

We have some array of integers $$$a_1, a_2, \dots, a_n$$$ with $$$n$$$ large (around $$$10^5$$$). We have to support the following types of operations:

  • Update: Select some subarray $$$[l, r]$$$ of $$$a$$$ and an arbitrary integer $$$x$$$, and add $$$x$$$ to each of $$$a_i$$$ for $$$l \leq i \leq r$$$. That is, we must be able to perform range addition. Note that $$$x$$$ can be both positive or negative.

  • Query: Count the number of integers at most $$$x$$$ in some subarray $$$[l, r]$$$ of $$$a$$$. Note that $$$x$$$ is allowed to change across queries.

Obviously, the interest is in subquadratic solutions. Fast online solutions (or offline) are interesting to me, and I'd be happy to know about them.

Thank you, NovusStellachan

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English NovusStellachan 2024-05-29 19:27:36 0 (published)
en2 English NovusStellachan 2024-05-29 19:27:21 301
en1 English NovusStellachan 2024-05-29 19:19:36 554 Initial revision (saved to drafts)