Samples —
3 1 4 2
4 2 1 3
According to the editorial we are taking pairs of indices which form a valid pair (Qj,Pi). All pairs are = (0,3)(1,0),(1,1)(1,2)(1,3)(2,0)(3,0)(3,1). [zero based indexing] Now we are sorting according to (i,-j).
New order of pairs is = (0,-3)(1,-3),(1,-2)(1,-1)(1,0)(2,0)(3,-1)(3,0). Now taking LIS considering only j's, we have ans as 4 but answer should be 2.
There is no clear explanation in the editorial, no C++ sample solution in the editorial and No english youtube video explaining this approach. I also tried to understand solutions of top rated coders but I think they have used fenwick tree.
Can anyone explain please I am stuck in this question since a day trying to understand this editorial.
