each Person has two attibutes A , B
for two diffirent persons i and j Ai<=Aj && Bi<=Bj then ith person is considered as inferior person & ith person will be removed from list if i and j have equal to case then one of them is removed from list this operation is executed when new Person is added to the list
there are two types of queries
1: add Ai,Bi to the list 2: show size of list
1<=N<=1e5 1<=Ai,Bi<=1e9
Sample Test Case:
5
1 1 3
1 2 1
2
1 2 2
2
Output:
2
2
For the remaining people in the list, if we sort their attributes $$$(A, B)$$$ by $$$A$$$ in increasing order, then the B will be in decreasing order. All of the values of $$$A$$$ will be distinct. Similarly, all of the values of $$$B$$$ will be distinct.
We can maintain this sorted list using ordered set.
Now we add a new person with attribute $$$(A_i, B_i)$$$. We find the $$$(A_j, B_j)$$$ pair in the list that satisfy $$$A_j \leq A_i$$$ and with largest possible $$$A_j$$$.
For example, we add $$$(A_i, B_i) = (3, 11)$$$ into the following list. Then $$$(A_j, B_j)$$$ is $$$(3, 9)$$$.
Next, we iterate down the list, and keep removing person with $$$B \leq B_i$$$. In this case, we can remove $$$(3, 9)$$$ and $$$(2, 10)$$$. If we remove at least one pair, we can add $$$(A_i, B_i)$$$ into the list.
Total complexity is $$$\mathcal{O}(N \log N)$$$.