Hi,I'm trying to solve this problem.It asks for point update and range query where the query is sum of distinct numbers in a given range.

Is this type of problem solvable by normal segment tree or do we need any kind of persistent data structure to do this?? I don't have much idea about persistent data structures.

Any help will be appreciated very much :)

Sorry, wrong.

There was theme about similar problem. But I have no idea how to adopt this algorithm to solve problem with update queries.

Ya I googled it and got the DQUERY link from codeforces.But with point update,this problem looks very tough.

Wrong :)

Old idea:

How to count distinct numbers in a range with update query?

For each position store next position with same value, and for each range query you have to calculate how many this stored positions have value > right border.

Example:

values= [1, 2, 3, 1, 2, 1, 3]nextposes= [4, 5, 7, 6,inf,inf,inf]query= [2, 6]nextposes= [5, 6, 7,inf,inf], 3 of them > 6, so answer is 3.Ok, you can do this operation with 2D tree in

O(lg(n)^{2})).You can update numbers in

O(lg(n)^{2})) too with same trees.Update operation simple and boring: you have to find previous&next elements with old value, update tree, after that find previous&next element with new value, and update tree after.

You can find this previous&next elements, if you will store positions for each value in:

map<int,set<int> > and use lower_bound on set.Only difference between this task and yours: your tree should return sum of values instead of count. If you implement 2D tree with SegTree+Treap, you can easily maintain this sum in Treap.

Hii yarrr

Thanks a ton.You really explained the approach very clearly.

Now,can you help me a bit on the implementation part?

I have implemented treap for solving ORDERSET in spoj.So I know basic split merge and find operations of treap.And I know seg tree operations.Now can you help me in implementing this 2D tree by combining treap and seg tree?Or can you give me some reference from where I can learn this??

Thanks a lot again for sparing your time to answer my question!! :)

what would be the space complexity for using 2d segment tree.

Another

O(log(n)^{2})-per-query solution (Sorry for my bad English).Maintain matrix

B= (b_{i, j}), whereb_{i, j}— answer to query Q i j. At first, the array and the matrix are zero. Init array using U ia_{i}.Processing U x y:

1) Set

a_{x}to zero: find left and right neighbor containinga_{x}— l and r. This query only affects suchb_{i, j}, thatl<i≤x≤j<r. They form a rectangle in matrix B, so just substracta_{x}of this rectangle.2) Set

a_{x}to y: similar to 1)2D BIT can do it, but I'm not sure it passes ML.

Hiii NuM.thanks a lot.I have got the idea.Can you help me a bit on the implementation part?

code

Hii NuM , thanks a lottt..I'm going to see this and try to learn the implementation just after this Div2 contest ends.

thanks again!!! :)

There is one more solution in sqrt(Q + N) * (Q + N), but it is also not easy to implement.

Hii goo.gl_SsAhv thanksss..can you explain What is the significance of the 'time' thing here??

it's query number in order of appearance.

ok thank youu :) Will try to understand this approach too :)

TL code.

Hi goo.gl_SsAhv thanks a lot.I'm seeing urs and NuM's approach right now.

Thanks again.

I was wrong. it's N^2. cycle after

`if (R >= L) {`

(line 186) kills everything.okay..