Some one can help me the this problem with T query. each query we have Val and Pos, we replace this Pos in array by Val then calc sum the count unique number in all sub new array. With array have 1e5 element, |val| <= 1e5, 1e5 query
Exmple
Help me pls, thanks
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
Auto comment: topic has been updated by rb235 (previous revision, new revision, compare).
Wouldn't happen to be this would it?
Hint: $$$f(l, r)$$$ is the number of unique value in range $$$[l, r]$$$. Denote $$$l_i$$$ as the nearest position on the left of $$$a[i]$$$ that $$$a[i]$$$ = $$$a[l_i]$$$, similar for $$$r_i$$$. $$$f(l_x, r_x)$$$ that $$$l_x > l_i$$$, $$$r_i > r_x$$$ and $$$r_x ≥ l_x$$$ will increase by 1.
Surprisingly, I have done this problem before, in case you have any trouble: code