The problem statement
For getting the answer somehow we need to have all the values , and we need to figure out a way to get those values in a special way because the most obvious approach is too slow in this case. So , Instead of looping and increasing every element in the given range we can keep do it in other way. We can keep an array with the name A , every element A[I] shows the difference between elements I and I-1 or in other words A[I]-A[I-1]. When we read an interval suppose it says from a to b. We add 1 to A[a] and subtract 1 from B[b+1] this way we can easily get the values.Now for getting the exact values of the elements we need to loop over and keep a variable num, num is 0 initially. for Calculate NUMBER[I], we add A[I] to num and NUMBER[I]=num. Then we need to use a fast sorting to sort them and output n/2+1 th element.Check the source code for a better udnerstanding.
For getting the answer somehow we need to have all the values , and we need to figure out a way to get those values in a special way because the most obvious approach is too slow in this case. So , Instead of looping and increasing every element in the given range we can keep do it in other way. We can keep an array with the name A , every element A[I] shows the difference between elements I and I-1 or in other words A[I]-A[I-1]. When we read an interval suppose it says from a to b. We add 1 to A[a] and subtract 1 from B[b+1] this way we can easily get the values.Now for getting the exact values of the elements we need to loop over and keep a variable num, num is 0 initially. for Calculate NUMBER[I], we add A[I] to num and NUMBER[I]=num. Then we need to use a fast sorting to sort them and output n/2+1 th element.Check the source code for a better udnerstanding.
No comments:
Post a Comment