# How to solve spoj SALMAN?

Can anyone explain how to solve SALMAN - Salary Management problem from SPOJ

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â€¦

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)

### 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 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

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 ??

#HERE is my accepted solutionâ€¦

@l_returns

No one answered for a long time, so I left hope and didnâ€™t check, I am going through it now.

okayâ€¦ npâ€¦

@l_returns

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.

https://pastebin.com/DGtkvzT5

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â€¦

@l_returns

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â€¦

@l_returns

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â€¦