Let us sort the segments so that \(a_1 \leq a_2 \leq \cdots\) holds.

◆ If \(a_i\) are all distinct

For simplicity, let us first consider the case \(a_i\) are all distinct.

In this case, we can choose Segments \(i\) and \(j\) simultaneously if and only if \(b_i < b_j\). Thus, the problem is equivalent to finding the length of Longest Increasing Subsequence (LIS).

Problem: Longest Increasing Subsequence (LIS)
For a sequence \(A = (A_1, A_2, \ldots, A_N)\), find the longest subsequence that is (weakly / strictly) increasing.

It is possible to find the length of LIS in \(O(N\log N)\) time (described below).

◆ Solution to the original problem

We can reduce the original problem to finding the length of LIS by carefully dealing with coincident endpoints.

Specifically, when sorting the segments, we will set a new rule for the case \(a_i = a_j\), as follows.

• When \(a_i < a_j\), we consider Segment \(i\) is smaller than Segment \(j\).
• When \(a_i = a_j\), we consider Segment \(i\) is smaller than Segment \(j\) if \(b_i > b_j\) additionally holds.

Since sorting and finding the length of LIS can both be done in \(O(M\log M)\) time, the problem can be solved in \(O(M\log M)\) time.

◆ Finding the length of LIS

We will explain two ways for this.

• Scan the sequence from left to right and let \(\text{dp}[x]\) be the greatest length of an increasing subsequence ending with \(x\) at that point. We can use Segment Tree to compute \(\text{dp}[x]\) fast. If \(x\) can be large, compress the values beforehand.

• Scan the sequence from left to right and let \(\text{dp}[k]\) be the smallest value that can be the last element of an increasing subsequence of length \(k\) at that point. We can use Binary Search to compute \(\text{dp}[k]\) fast.

◆ Sample implementations

• https://atcoder.jp/contests/arc126/submissions/25740361
• https://atcoder.jp/contests/arc126/submissions/25740412