# | User | Rating |
---|---|---|

1 | Benq | 3650 |

2 | Radewoosh | 3648 |

3 | tourist | 3579 |

4 | ecnerwala | 3551 |

5 | Um_nik | 3494 |

6 | Petr | 3452 |

7 | ksun48 | 3432 |

8 | jiangly | 3349 |

9 | maroonrk | 3338 |

10 | Miracle03 | 3314 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 210 |

2 | awoo | 188 |

3 | Errichto | 186 |

4 | rng_58 | 185 |

5 | SecondThread | 182 |

6 | Ashishgup | 176 |

7 | Um_nik | 175 |

8 | maroonrk | 173 |

9 | antontrygubO_o | 171 |

10 | -is-this-fft- | 168 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/16/2021 09:39:47 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Ok so first of all, lets talk about

`set`

and`ordered_set`

,`set`

saves values in some order (usually increasing order), but you cant take the "index" of some value, for example, if we declare`set<int> = {2,3,9,7}`

, we know that the "index" of 9 is 3, and "index" of 7 is 2, but there is no methods that you can call to get that "index".So if you want to know the index of some ordered values, you can use the

`ordered_set`

(in this code is used as`os_set`

) that as the`set`

, save the values in some order, and has a method called`order_of_key()`

that does exactly what we need, give the index of some value.Now, lets talk about the ideia of the question: Lets supose that in one query the value asked is A, and A appear K times in the array, you will look to the first appearance of A, show his index, and than move A to the start. So if you query for the same A again and again, you will always look to the same first appearance of A, never looking for the others K-1 A's in the array, so doesnt matter if A appear K times, you will only need the first appearance of A.

So, the idea in this solution is to save the first appearance for all A, as in

`if (!id.count(a)) id[a] = i;`

, then save all the indexes of the array in an ordered_set, as in`ost.insert(i);`

. Then, for all queries, we look for the index of A, lets call it B, and then search the index of B in the`os_set`

, after this, we remove B of the`os_set`

, and add the new index as the lowest index at the moment.At the start, the indexes look as 0 to n-1, after the first query, the lowest index will be -1, then -2, and so on.

For the sample, we have the array as

`2 1 1 4 3 3 1`

, index of all distinct values are:`(2,0), (1,1), (4,3), (3,4)`

, and the`ordered_set`

has all the indexes`{0,1,2,3,4,5,6}`

. Then, we query for 3, its index is 4, the index of 4 is 4 in the os_set. So the answer is 4 + 1 = 5 (as the question is 1-indexed). Then we remove the index 4 to the`os_set`

and update the index of 3 as -1.`(2,0), (1,1), (4,3), (3,4)`

changes to`(2,0), (1,1), (4,3), (3,-1)`

and`{0,1,2,3,4,5,6}`

changes to`{-1,0,1,2,3,5,6}`

(erase 4, add -1).We query for 2, its index is 0, so we ask for index of 0 in the

`os_set`

, and the answer is 1+1 = 2. We again remove 0 of the`os_set`

and add -2, as the new index of 2.`(2,0), (1,1), (4,3), (3,-1)`

changes to`(2,-2), (1,1), (4,3), (3,-1)`

and`{-1,0,1,2,3,5,6}`

changes to`{-2,-1,1,2,3,5,6}`

. (erase 0, add -2).And so on.

I hope this helps you, sorry for my poor english.

got it, thank you bro :)