Does someone can help me solve this problem? Click here to the problem It's a problem about Lis , I think this problem is interesting , but I cannot solve it. Thanks in advance.
Problem means: You are given an array $$$p$$$ of length $$$n$$$ , each $$$p_i$$$ is in the range of $$$[L_i,R_i]$$$ . What is the length of the longest increasing subsequence of this array? $$$1 \leq n \leq 3 \times 10^5, 1 \leq L_i \leq R_i \leq 2 \times 10^9 $$$
Auto comment: topic has been updated by NNewbie (previous revision, new revision, compare).
Let $$$dp[i][j]$$$ denote the minimal value of last element in increasing subsequence with length $$$j$$$ of $$$p_1, p_2, \ldots, p_i$$$. If there is no such subsequence then set $$$dp[i][j] = INF$$$.
We can easily calculate this $$$dp$$$ in $$$\mathcal{O}(n^2)$$$. Because $$$dp[i][j] + 1 \le dp[i][j + 1]$$$ (assuming $$$INF + 1 = INF$$$) we can avoid maximum in few cases in transitions. We have following transitions:
$$$dp[i + 1][j] = L_{i + 1}$$$ if $$$dp[i][j] > L_{i + 1}$$$ and $$$dp[i][j - 1] < L_{i + 1}$$$
$$$dp[i + 1][j] = dp[i][j - 1] + 1$$$ if $$$L_{i + 1} - 1 \le dp[i][j - 1] \le R_{i + 1}$$$
$$$dp[i + 1][j] = dp[i][j]$$$ otherwise.
We can notice few things — we will use first transition on at most one element $$$j$$$ and transitions of second type will be used on interval. It is enough to use BST with fast merge and split (for example treap) to achieve $$$\mathcal{O}(n \log n)$$$ complexity.
There is also a solution with same $$$dp$$$, but without treap (or any other BST), but it is a little bit more complicated.
Hi , Thank you for answering my problem. According to your idea , I get 70 points with this code : https://paste.ubuntu.com/p/RKhzy6rndm/ . But I don't know how to solve it with $$$O(nlog_n) $$$ complexity. Can you explain more detailly ? It's better to show the code of the solution that with $$$O(nlog_n) $$$ complexity. Sorry for my poor English.