The result of the query [a, b] is the number of integers, the last occurrence of which [1, b] → = a.
Suppose we have a query (2; 4) for the sequence from the example: [1, 1, 2, 1, 3]. To make a set from the multiset [1, 2, 1], we can calculate the last positions of numbers from 1 to b and select only those>> a. Thus, these cases in this example are 4 (for 1) and 3 (for 2). Both of them> = 2 = a, so the result is 2.
How to effectively store all the last occurrences and be able to quickly find all of them that are = = a? In a tree (spacing tree or segmented tree). I would use the BIT (Binary Indexed Tree aka Fenwick Tree) described here .
But first we have to put things in order. What events? An event is either a number at a certain position (therefore, a pair (x; y), where x is a number and y is a position) is NumberEvent - or an interval (pair (a; b)) is a QueryEvent. We must sort our requests. First we need to consider numbers without adding them to tree queries, it makes no sense. So, we want to start from the first position (so we sort the NumberEvents by the positions - y). The first position is 1. We remember that last_position 1 = 1, and we add position 1 to the tree. Then we have 1 at position 2. We check last_position 1 and it is not empty, so we delete position 1 from the tree, add position 2 to the tree and update last_position 1 = 2. Then we have 2 at position 3. We check last_position 2 and it is empty, so we have last_position 2 = 3 and add 3 to the tree. Then we have 1 at position 4. We remove position 2 from the tree, add 4 and update last_position 1 = 4. And now something else. We see that we have a query with b = 4, and we examined all the numbers from the positions [1; b]. All that remains is that we calculate the positions in the tree that> = a = 2. There are 2 of them: 3, 4. We remember that for (2; 4) the result is 2 (we must print it in good order, therefore instead of (2; 4) I would recall the query as (2, 4; 2), since this was the second query, and in the end I printed all the queries from 1 to q). And so it is. Therefore, sorted requests:
1 1 NumberEvent [number;position] 1 2 NumberEvent 2 3 NumberEvent 1 4 NumberEvent 2 4 QueryEvent [a;b] or [i;j] from the task - sorted by b 3 5 NumberEvent 1 5 QueryEvent 3 5 QuertEvent
Sorting and combining all q + n queries takes (q + n) log (q + n) time. Then for each q + n queries we use log (n) time (because there are no more than n numbers in the tree). The total complexity is then equal to O ((q + n) log (q + n)).
As for tree operations.
I will describe my description on this Polish site. There are good images and codes.
Indexing: If we want to have an interval tree for numbers from the range 0..x, we must first round x to the power of 2, subtracted by 1. So, for x = 5, we change x to 2 ^ 3-1 = 7. The intervals are similar to the image from the link. For instance. for the range 0..7 and for the interval 4..5, the index is 6 (we calculate from 1, not 0).
Adding / subtracting a value: Suppose we want to add a number 5 to a tree with a range of 0..7. An interval of 5..5 index is 5 + 2 ^ 3 = 13 (since we have values from a range of 0..2 ^ 3 -one). Therefore, we update the tree [13] + = 1 (the first tree [] is all 0). We are moving up to the interval, which includes 5..5 and 4..5 with the index (13/2) = 6 (check it in the picture below). We also need to update it so that we use tree [6] = tree [2 * 6 = 12] + tree [2 * 6 + 1 = 13]. Then: tree [6/2 = 3] = 1, tree [3/2 = 1] = 1, and then we have 1/2 = 0, so we stop (as I said - count the indices from 1, so that, when we have 0 we exit the loop). The time of adding a number is logarithmic (each time we divide by 2 numbers). We can subtract the number from the tree in the same way. Just subtract 1 instead of adding.
Query: We can check how many numbers are in the interval a..b also in logarithmic time. We are interested in the numbers> = a, so the result is a query (max.) -Query (a-1). Max in our case is equal to n, since we store positions in the tree, and they are in the range 1..n. Therefore, we are interested in the query (n, a-1). How to calculate the request? First add n and a-1 number 2 ^ 3 (for range 1..x) to get the intervals n..n and a-1..a-1. Then we add the tree [a] (where a = a-1) or the tree [b] (where b = n) to the result, and a = b. If a% 2 = 0, then a is the right child, and we add it. Also b% 2 = 1, then b is the left child. We are interested in the left child elements of b, because otherwise they will be larger than b, so they will be out of reach. Same thing with a. Left children a are out of range.
You can see the codes for the request and insert the link.
If in doubt, ask.