How can I solve query problems like "count the number of different elements in [l, r]" on array?
Разница между en2 и en3, 3 символ(ов) изменены
sometimes I saw — unfortunately, I can't remember where I saw that — problems like below. I simplified the statement for clarity.↵

Problem)↵

 You're given an array A with N elements, (A[0], A[1], ..., A[N
-1]). and there are two kinds of queries↵

  * 1 x y : change A[x] to y↵

  * 2 l r : count the number of different elements in A[l], A[l+1], ..., A[r].↵

Condition)↵

  * 1<=N, Q<=100,000 (Q: total number of queries)↵

  * 1<=A[i]<=10^9 + 9 (A[i] : integer)↵

I tried to approach with segment tree but still have no idea.. How can I solve this kind
s of problems? 

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский nyan101 2016-11-21 03:15:18 3
en2 Английский nyan101 2016-11-21 03:14:11 14
en1 Английский nyan101 2016-11-21 03:13:44 670 Initial revision (published)