Problem, the multi said.
All right, so what do we have here?
We are given a multi set, right?
We are given an integers initially and queue queries.
Right.
And these integers basically are a multi set right of integers.
And in these queries, we have two possible updates.
Right.
We have two possible operations.
And those are.
The first one is that you can insert an integer into the multi set.
As simple as that.
The second one is that you take the Kafe or the statistic and remove it from the multisite so you can
see this Malti said one four two one four five seven, which is sorted.
One one two four four five seven.
Here, the fourth element, the fourth order statistics is to write.
So these are basically your updates or queries, however, want to call it you either other element
or remove some order statistic.
So yeah, this question is not that hard, but it could be a little bit tricky.
First time you think about it.
And it basically goes like this, like I've read the problem and I thought about.
All right.
So it asks me to perform all of these operations and then I should print some integer, which is in
the multi set if the multi set is not empty.
So let's think about is how can I insert elements fast?
That's not as hard, right, inserting elements is quite easy because you can do this with a regular
set.
Right.
Like, you can literally take the statement of the problem and like convert it into code and just have
a multi set, do the job for you.
The problem is with the second thing, because you have to find the cave order statistics, remove it.
And then, of course, continue the process.
So the first thing I thought, can I do this?
Have a set to like if I can do the first thing, maybe the second thing also is doable in the set.
But it's not because in a set you are able to bind the research value of some element.
So if you have value X and you want to find where this value you, you want to find the position of
the value.
That's cool.
You can do that lower bound, upper bound, whatever you want.
But the reverse is not doable.
Right.
So from value to position.
Yeah.
Good job.
Go on.
You are free but from position to value.
Now it's impossible.
So a multi set is not able to do this job for me.
And then I thought like.
All right.
So I am not able to do this with a multi set.
What kind of data structures do I know which kind of simulate the same principle of the multi set?
The multi set is able to keep my elements sorted increasingly or decreasingly and maybe find some value
if buying the research.
But the main point of the multi set is that it is able to store those elements increasing or decreasing.
You can insert.
You can remove.
It is still going to be increasing or decreasing after those objects.
So I need something like that.
And this is the tricky part.
Of course, if you can do this with a set, you can do this with something like another set or priority
queue.
But the recent data structure, which is still a binary tree, as I said, is.
And performs updates and queries in Bigo of Log.
And that is the Fenwick tree.
Or the binary index three or the segments.
And because.
The binary tree is not as powerful as the segment tree.
I mean, it's more elegant, it's more easy to write, but not as powerful.
Usually, if you can solve something, have a binary index tree.
You can also do it.
We have a segment tree that makes sense, right.
So I thought about segment trees.
I'm like immediately.
I need to do updates and queries really quick.
I mean, no queries like returning values.
But yeah, this kind of updates really quick and then get an element.
So how would I do this job using the segment?
Basically, I need to find the Kafe element in increasing order in Bigo of Log using the segment tree.
You can store a segment tree, but not for the initial array.
So not for indices, not for positions, but for values.
You can store a segment tree for values.
And in that segment tree with the use of that segment tree.
You are going to find out how many values are less or equal than some value or in some range of values.
And yeah, let me explain what I mean by that.
Right.
So let's say you have got not the code.
All right.
Use let's say you have got the array one.
One, two, three, four.
I think there was another one.
Yeah, right.
Good.
This is your story, right?
Again, news a segment three.
As you can see, unary is defined by its indices, right?
So on each index, you have got a value.
We won't use the segment three.
Just like disarray to compute something on Sudbury's or on the ranges of indices.
But on the ranges of values, this is super important.
And let me tell you what I mean by that.
We will have a segment three.
That is going to have each and every value between between between one and end.
Then I checked the statement, oh, look at this.
Each and every value is between one and end.
Each and every inserted value is between one and end.
So I can use a secondary.
For the values between one and end, so what is the information that I should store for each node?
Let's start with the lives.
What should I store for each of these values?
How many elements are of that value?
This is exactly it.
So let's take this example.
I have four values.
So one, two, four.
Right.
So let's erase this.
I don't need this.
Let's do it a little bit bigger to see better.
All right.
So how many values of how many elements of value?
One I have free.
How many of value to one free one.
And for one.
Right.
So these are the leaf's in my segment three.
Three elements.
One element, one element, one element.
Cool.
What should their father's store?
How many elements have a value?
Between one and two.
Three plus one, right?
So for.
So as you can notice, here is just a basic some segments.
We just compute the sum between the sons to know the value in some not.
Right.
So, yeah.
How many values are between value?
How many elements have value between three and four.
One plus one is to call.
And how many values, how many elements have the value.
Between one and four.
Six.
Yeah, initially.
The value in the route is, of course, going to be equal to the number of values of elements in the
array.
That makes sense, right?
Because every element has a value between one and it.
So basically, you build this segment tree in which the information in the node.
Is so let's get some I dunno, let's call it counter, actually.
Yeah.
So the information in the note, let's call it counter of note.
Let's say this mill.
Is correspondent to the Saberi, to the sub range of values.
Sorry, not Saberi.
Some range of values.
Right.
The signatory is for values to the sub range of values from R, from L to R..
This means that counter of note is the number of elements in the array which have a value.
So the number of, let's say, elements of AI, which have a value between L and R.
The whole array.
Right.
So you're probably asking yourself, all right, Andy.
We can build this segment three.
I won't get into details about segment trees, but knowing the basic theory, you can build this segment
tree.
You can update for each and every element.
Or you can code some build function and call that once.
That's cool.
But how do we use it?
We are going to use this.
To find the value of the cave or their statistics, can you imagine how it's not that hard?
Let me show you.
And of course, I'm going to show you on this example, not let's not remove the array.
Let's go.
All right.
So we have this segment three, right?
Six four, two, three, one, one.
Let's say I want to find the fifth.
The fifth.
So K equals five.
Element in this multi set.
Right.
You can see that here it is sorted.
But it's not gonna be sorted, right?
Not initially, especially.
So I want to find the fifth order statistics.
What do I do?
They go to the root and they see, hey, root, how many elements are there?
We value between one and four.
Six.
Oh, OK.
So I'm gonna have my value here in this obce could well I mean, the root I checked the left son.
Hey, left son.
Many values do have between one and two.
Four of them all.
I want the fifth value.
OK, I have to go to the right son.
I'm gonna go to the right side, and because I know the smallest four values are in the left son.
Now, in the right sun, I am looking for the fourth smallest value.
Or, of course, the smallest value.
So I'm looking for the smallest value now in this subject.
Hey, right, son.
How many values do you have?
Two.
Oh, perfect.
Cool.
So my values here then in this one.
Hey, Lifeson, how many values do you have?
One.
Oh, cool.
I am looking for one.
So the value is here.
And then of course when I'm in a leaf.
The value of the leaf is indeed the answer that I am looking for.
And this is how can solve this problem, this classic problem of a multi set in which you insert elements
and ask for the cough statistic, order or order statistics, whatever.
This is how we solve it using segment three.
You just need the segment three that is going to tell you how many values.
Between some left and some right, do you have?
When we have queries of the first type.
So first type queries.
We just have to insert some element.
So we will perform an update.
Value X, we've plus one.
Research for the leaf.
We value X, we increase its value by one end, of course, our each and every father on the second
query.
Now we will perform a query that is going to tell us, hey, what is the calf?
The smallest element.
Which, of course, we do recursively using the segment three.
And because the number of iterations, we will always move into a sun, either left or right, either
left or right.
So the maximum number of iterations is the maximum height of the segment three, which is.
Which is.
Which is Bago of Log.
Take one trees have height of Bego of law that we perform query of key and embargo of log.
We find that the leaf that value that Kaif smallest value.
And then we perform an update.
Let's say this returned Val Val and minus one because you have to remove it.
We say find me the put the value Val and tell and tell it that you have one less element right now and
that's it.
That's it, after performing all of this.
You just look in the root and ask the root hatred, how many voters do we have now?
If it says zero, you return zero because there is no element in the multisite, if it says greater
than zero.
You say, oh, cool.
Give me the smallest value.
So far, the answer.
You use, again, the query function.
Only if the route is positive and that's it gets big of log, bigger of log.
The goal of log.