### NNewbie's blog

By NNewbie, history, 6 weeks ago, ,

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$

• +12

 » 6 weeks ago, # |   0 Auto comment: topic has been updated by NNewbie (previous revision, new revision, compare).
 » 6 weeks ago, # |   0 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.
•  » » 6 weeks ago, # ^ |   0 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.