a_few_what_ifs's blog

By a_few_what_ifs, history, 4 weeks ago, In English

Hi everybody! I am new to CF community and recently came across with this problem, what can be the solution for it? Any help is appreciated!

There is an array of length $$$N$$$ consisting of numbers and array is one-indexed from $$$1$$$ to $$$N$$$. There are three types of operations :

1) Add $$$1$$$ to the number at index $$$A$$$,

2) Print the number of numbers that is bigger than or equal to $$$X$$$,

3) For all of the numbers bigger than or equal to $$$Y$$$, subtract $$$1$$$ from them.

Initially, any number in the array is at most $$$10^8$$$. Array length $$$N$$$ and number of operations $$$Q$$$ is at most $$$10^5$$$.

Sidenote : Although I knew CF (I read the blogs, they're quite helpful) I didn't have any account till now and decided to open one to ask the question above. That is kinda out of scope but I don't know if newcomers' questions are welcomed and I apologize if I've done something wrong with the format or website rules.

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

4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you are asking for this one right ??

4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

I didn't implement the details of this solution, but I believe it should work:

The key observation is that operation 3 does not actually modify the relative ordering of all N elements, but only modifies the number line on which they are placed, by turning intervals of width 1 into width 0, so if we can keep track of where these skips occur, we can simply perform all desired operations on the original number line. Therefore, we can just maintain two binary search trees, one for the initial numbers, and one for all skipped intervals. Let $$$\text{query}(x)$$$ be the number of skips less than a given value x. We can now define a function $$$f(n)$$$ to translate from a queried number $$$n$$$ to its corresponding "original" value (i.e. where it should be on the original number line, relative to other elements), by binary searching for the largest point $$$m$$$ satisfying $$$m-\text{query}(m)=n$$$ (we must do largest to ensure that, when handling type 3 below, we do not skip any interval twice).

Now, all operations become doable. For type 3, we insert $$$f(Y-1)$$$ into the tree of skips, since we are skipping the interval $$$(Y-1, Y)$$$ on the modified number line, so converting $$$Y-1$$$ will tell us where this interval is in our original number line. For type 2, binary search to find where $$$f(X)$$$ sits in our sorted tree of original values. For type 1, we must maintain an additional set of pointers, going from array indices to nodes in our sorted tree, so we can access element A in $$$O(1)$$$. Now, we take it's original value $$$n$$$, translate it to the modified number line as $$$n'=n-\text{query}(n)$$$, and then remove the node and insert a new node with value $$$f(n'+1)$$$.

Thus each query can be handled in log time, so the runtime is $$$O(n+q\log n)$$$.