Can anyone explain how to solve SALMAN - Salary Management problem from SPOJ
It is DFS + SEGMENT TREE + LAZY PROPAGATION…
Moreover it is DFS + SEGTREE FOR SUM + SEGTREE FOR MIN + LAZY SEGTREE…
first of all DFS part is just one time per each test case…
A)DFS PART
Traverse over the TREE (DFS is must… BFS is not allowed) as we do normally… and while doing it make 3 arrays
1)(let’s call it id[]) and store the IDs in it as per the order we traverse it…
i.e. assign root as 1 , then its leftmost child 2 and then its(of left most child of root) as 3 and so on…
2)(let’s call it s[])inverse of previous array
3)(let’s call it e[]) new id of the last leaf under that node…
Taking example given in question:
Click to view
Now in this image let me give you new id assigned to each…
#oldID \rightarrow NewID
1 \rightarrow 1
2 \rightarrow 2
7 \rightarrow 3
6 \rightarrow 4
3 \rightarrow 5
5 \rightarrow 6
4 \rightarrow 7
#so this column one will be stored in id[]…
i.e id[1]=1 , id[2]=2 , id[3]=7 , id[4]=6 , … you can keep it 0-indexed if you want to…
#column 2 will be stored in s[]
i.e s[1]=1, s[2]=2 , s[7]=3 , s[6]=4 ,…
#e[] will be
e[1]=s[4]=7 , e[2]=s[6]=4 , e[3]=s[5]=6 ,e[4]=s[4]=7 , e[5]=s[5]=6 ,e[6]=s[6]=4 , e[7]=s[7]=3
B)Segtree part with Lazy Propagation
Consider this as question of segment tree with range update query (adding/updating a range of nodes at a time with a value)
I advice you to look at lazy propagation in segment tree first If you haven’t used it still…(its for saving us from tle)
Here we are using two segment trees having similar structure(remember both will have lazy propagation and both will be updated at a time hence they are not different)…
YOU CAN CONSIDER IT AS A SEGTREE WITH TWO INTEGERS PER EACH NODE OF TREE…
1) ParentNode = LeftChild + RightChild;
2) ParentNode = min(LeftChild , RightChild);
BASE(LEAF) DATA for segtree
Click to view
this segment tree will be salaries of the employees as per
id[] array… that means in order of
#salary[id[1]] , salary[id[2]] , salary[id[3]] , salary[id[4]]…
which would be
#salary[1] , salary[2] , salary[7] , salary[6] ,…
Now You might be thinking that why we make segment tree with such order of salary and that 3 arrays… well there is a reason…
Now if i ask you to update salary of 2 then I need to update it from node s[2] to e[2] (i.e 2 to 4 hence salary[2] , salary[7] , salary[6])
so here we got what we wanna do…
We just updated employees under employee id2 including employee id…
Now what to add to salary…
For this purpose we made 2nd segtree(minimum one) just find the minimum salary as we saw the update… and take min(query,1000) and add it to all of them using the technique we discussed above…
This is how we can get AC in this que …
3 Likes
An image is missing from that page and I am also not able to understand the question properly 
…
Though I ll try and get back to u…
okay I had a talk with Faiyaz (the author of the question)…
Now the image issue is fixed…
This question included various things like
#1) DFS
#2)Two Segment Trees ( a) range sum query b) range min query )
#3)Lazy Propagation
Hence I recommend to try this concepts individually before solving this problem…
Where are you @arpit728… bro it took 1 hour for me to write this answer and some more to understand the question and answer… please read it bro…
What software did you use to make the image? I have a guess but want to be sure :3
its given inside the que 
I would like to know what was your guess ??
No one answered for a long time, so I left hope and didn’t check, I am going through it now.
okay… np…
Thank you so much, for taking time and solving this problem you have really explained it nice and made it simple for me to understand such a difficult problem.
I coded this, but I am getting wrong answer can you please help me with this, below is the link to my code.
Welcome and thanks bro
I think u haven’t used lazy propagation before this question… Lazy should be updated even if the query is out of range in update query and it should also be done in query for finding min and sum if it is inside the range.
I think you haven’t done that in query part… try to refer my code once and you’ll get it… Do let me know if u have any query further
Lazy needs update in both update and query for getting value… it’s like we are lazy but we have to do that when we need a particular answer…
Since the question itself was a big one hence I skipped the explanation of lazy part… u can read about it on Google easily… videos are also available…
Yes I have less experience with lazy propagation. In my query function if you will look closely you will find that I have called shift() function which internally propagates the values to its children. I think that should not be a problem.
“Lazy should be updated even if the query is out of range” why?
Okay sorry I forgot to see shift function…
Because consider I have n=4 so tree is [1,4] [1,2] [3,4]…consider all of them 0 intially…
Now I did lazy update in range [1,4] of value by 2… Then [1,4] will become 8…
And lazy of both child will be 2 [1,2] [3,4] …
Now again I call update function of [1,2] by 1 so u ll first do lazy update of [1,2] so [1,2] will become 4 and then again add 2 for update… Hence it ll become 6… fine… But [3,4] segment is still 0…
Now u ll update parent by node1_4 = node1_2 + node3_4 = 6 + “0” which is wrong…
So u don’t need to traverse in nodes out of range… But u do need to upadte them so that parents value will remain true…
When you do a lazy update on range [1,4] of value by 2. Then [1,4] will become 8 and lazy of both child will be 0. Now again you call update function of [1,2] by 1 so first you will call shift function and lazy of both child will become 2. then again lazy of node[1,2] will become 6 node1_4=node1_2+node3_4=6+4=10.
when did you made node3_4 = “4” ???
as query were 1_4 and 1_2 only…
I think according to ur code node3_4 won’t get updated until we call any query which has an intersection with 3_4
that is why I am asking to update 3_4 in update query even though It is out of range…
though let me check you code thoroughly… I can be wrong…
I ll get back to you after checking…