| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
hello everyone,
Recently i came across this problem http://www.spoj.com/problems/DQUERY/en/. I solved the problem using Mo's algo and BST which is basically offline solution. Is there a way I can solve for each query online (and similarly for trees that involves queries on the subtree of its nodes)? If yes, please help me out.
Thanks in advance!!
Auto comment: topic has been updated by Code_sprinter (previous revision, new revision, compare).
You can use merge Sort Tree to solve this problems. Here you can see sample code of merger sort tree
You could use a BIT (segment or fenwick tree) of size 1e6 and update the positions of the a[i] setting that to 1. Then query the range will tell the number of distinct elements.
Edit: But more simple would be to use prefix sums on an array of size 1e6.
I didn't get how you gonna solve query with that.
Can you please elaborate a bit on how to get answer for any given
landrusing segment or fenwick tree?Well, a simple BIT returns the sum of elements in the query range. Since the values of a[] are limited to 1e6, we use a BIT of size 1e6.
Then set the values in the BIT at positions of all a[i] to 1. Note that if two a[i] are same, we maybe twice set the value at position a[i] to 1. We could implement this update as query of that position, and only update if it is 0.
Then the query of a range l,r will return the sum of the numbers in that range. Since the sum of the ones equals the number of the ones, it is the number of distinct elements.
But as written, doing the same on a prefix sum array would be simpler. I was irritated by the meaning of offline.
Hey! We have to answer distinct numbers present between
a_landa_rand not betweenlandr.Ok, please forget what i wrote :/
But I googled it, and found an explanation on stackoverflow how the problem can be solved.
What an interesting coincidence!! Codechef has a very similar problem : https://www.codechef.com/JUNE20A/problems/DIFVAL
Please wait a few days more for contest to get over and you can read the editorial.
Feel free to research on your own till then, but please refrain asking someone about it since other contestants might get solution without working for it.
You can use persistent data structures like persistent segment tree
Yes! You can use Persistent Segment Tree for online answering to queries.
You need to keep roots of versions and last positions for each value.
1. Preprocessing:
2. Answering to queries
Exactly
Could u elaborate again, I could not understand the above explanation.
Alright. Firstly, you need to know using Persistent Segment Tree (update, etc.). Secondly, you need to keep only roots of updated versions in
versionsarray. Thirdly, as I said above you should put 1 only in last seen position of current value (it means, keep positions in arraylastand do 0-1 update on positions). Fourthly, because of updating last position inr, we take answer fromversion[r]betweenlandr.Also, you may see my solution for better understanding.
thanks, that means each query can be answered in logn time online which is better than using merge sort tree where it takes (logn)^2 for each query.