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 = (bi, j), where bi, j — answer to query Q i j. At first, the array and the matrix are zero. Init array using U i ai.
Processing U x y:
1) Set ax to zero: find left and right neighbor containing ax — l and r. This query only affects such bi, j, that l < i ≤ x ≤ j < r. They form a rectangle in matrix B, so just substract ax of this rectangle.
2) Set ax 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..