rb235's blog

How to calc sum the count unique number in all sub array?
By rb235, 3 years ago, In English

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

inp
out
Explain

Help me pls, thanks

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Wouldn't happen to be this would it?

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like 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

→ Reply