Amer_Oniza10's blog

Find the count of distinct numbers in a range
By Amer_Oniza10, history, 2 months ago, In English

Hi ... Is there a way to find the number of different integers within a range of log(n) complexity?

  • Vote: I like it
  • -21
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it -6 Vote: I do not like it

use a map may be bro

→ Reply
»
2 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Use a segment tree. Whenever you add a new element set its value as 1. When you want to know how many values in range [l,r] you can get the sum of the range (l,r)

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hint: Offline+Fenwick.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://cses.fi/problemset/task/1734

→ Reply
»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

make array nxt[i] that means index of number that equal a[i] if there are no such set INF

then for answer u need to find number of nxt[i] that less r on range l<=i<=r

use Segment tree

→ Reply
»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Hello freind you can simply use 1 pointer technique to solve this. Move your lazy ass pointer finger and count whatever you want in the segment

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Persistent segment tree if you need online, else Fenwick and offline

→ Reply