H. Ice Baby
binary search; brute force; data structures; dp; implementation; sortings
The longest non-decreasing subsequence of an array of integers \(a_1, a_2, \ldots, a_n\) is the longest sequence of indices \(1 \leq i_1 < i_2 < \ldots < i_k \leq n\) such that \(a_{i_1} \leq a_{i_2} \leq \ldots \leq a_{i_k}\). The length of the sequence is defined as the number of elements in the sequence. For example, the length of the longest non-decreasing subsequence of the array \(a = [3, 1, 4, 1, 2]\) is \(3\).You are given two arrays of integers \(l_1, l_2, \ldots, l_n\) and \(r_1, r_2, \ldots, r_n\). For each \(1 \le k \le n\), solve the following problem: Consider all arrays of integers \(a\) of length \(k\), such that for each \(1 \leq i \leq k\), it holds that \(l_i \leq a_i \leq r_i\). Find the maximum length of the longest non-decreasing subsequence among all such arrays.
Each test consists of multiple test cases. The first line contains a single integer \(t\) (\(1 \leq t \leq 10^4\)) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer \(n\) (\(1 \leq n \leq 2 \cdot 10^5\)) — the length of the arrays \(l\) and \(r\).The next \(n\) lines of each test case contain two integers \(l_i\) and \(r_i\) (\(1 \leq l_i \leq r_i \leq 10^9\)).It is guaranteed that the sum of \(n\) across all test cases does not exceed \(2 \cdot 10^5\).
For each test case, output \(n\) integers: for each \(k\) from \(1\) to \(n\), output the maximum length of the longest non-decreasing subsequence among all suitable arrays.
In the first test case, the only possible array is \(a = [1]\). The length of the longest non-decreasing subsequence of this array is \(1\).In the second test case, for \(k = 2\), no matter how we choose the values of \(a_1\) and \(a_2\), the condition \(a_1 > a_2\) will always hold. Therefore, the answer for \(k = 2\) will be \(1\).In the third test case, for \(k = 4\), we can choose the array \(a = [5, 3, 3, 3]\). The length of the longest non-decreasing subsequence of this array is \(3\).In the fourth test case, for \(k = 8\), we can choose the array \(a = [7, 5, 3, 5, 3, 3, 3, 3]\). The length of the longest non-decreasing subsequence of this array is \(5\).In the fifth test case, for \(k = 5\), we can choose the array \(a = [2, 8, 5, 3, 3]\). The length of the longest non-decreasing subsequence of this array is \(3\).