Number of distinct elements in a subarray(solving online)

Блог пользователя Code_sprinter

Автор Code_sprinter, история, 6 лет назад, По-английски

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!!

Code_sprinter
6 лет назад
15

Комментарии (15)

Написать комментарий?

Code_sprinter

6 лет назад, скрыть # |

Auto comment: topic has been updated by Code_sprinter (previous revision, new revision, compare).

→ Ответить

Mujahid_Cou

6 лет назад, скрыть # |

You can use merge Sort Tree to solve this problems. Here you can see sample code of merger sort tree

→ Ответить

spookywooky

6 лет назад, скрыть # |

← Rev. 2 →

-6

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.

→ Ответить

shubhammitt

6 лет назад, скрыть # ^ |

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 l and r using segment or fenwick tree?

→ Ответить

spookywooky

6 лет назад, скрыть # ^ |

-6

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.

→ Ответить

shubhammitt

6 лет назад, скрыть # ^ |

Hey! We have to answer distinct numbers present between a_l and a_r and not between l and r.

→ Ответить

spookywooky

6 лет назад, скрыть # ^ |

← Rev. 2 →

Ok, please forget what i wrote :/

→ Ответить

spookywooky

6 лет назад, скрыть # ^ |

But I googled it, and found an explanation on stackoverflow how the problem can be solved.

→ Ответить

forgotter

6 лет назад, скрыть # |

+11

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.

→ Ответить

CoderAnshu

6 лет назад, скрыть # |

You can use persistent data structures like persistent segment tree

→ Ответить

orangeorange

6 лет назад, скрыть # ^ |

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:

    For each position i:
      - if we meet a[i] for first time, add 1 to position i
      - else add -1 to position of last a[i] and add 1 to current position

2. Answering to queries

    Query: Left, Right

    We take sum from position Left to Right from version of Right position. Sum of ones in this segment will an answer for current query.

→ Ответить

CoderAnshu

6 лет назад, скрыть # ^ |

Exactly

→ Ответить

Code_sprinter

6 лет назад, скрыть # ^ |

← Rev. 2 →

Could u elaborate again, I could not understand the above explanation.

→ Ответить

orangeorange

6 лет назад, скрыть # ^ |

Alright. Firstly, you need to know using Persistent Segment Tree (update, etc.). Secondly, you need to keep only roots of updated versions in versions array. Thirdly, as I said above you should put 1 only in last seen position of current value (it means, keep positions in array last and do 0-1 update on positions). Fourthly, because of updating last position in r, we take answer from version[r] between l and r.

Also, you may see my solution for better understanding.

→ Ответить