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 kinds of problems?
↵
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
