Description

　　Mary在她的生日禮物中有一些積木。那些積木都是相同大小的立方體。每個積木上面都有一個數。Mary用他的 所有積木壘了一個高塔。媽媽告訴Mary游戲的目的是建一個塔，使得最多的積木在正確的位置。一個上面寫有數i 的積木的正確位置是這個塔從下往上數第i個位置。Mary決定從現有的高塔中移走一些，使得有最多的積木在正確 的位置。請你告訴Mary她應該移走哪些積木。 Input

　　第一行為一個數n，表示高塔的初始高度。第二行包含n個數a1,a2,…,an，表示從下到上每個積木上面的數。 (1<=n<=100000,1<=ai<=1000000)。 Output

　　注意：請輸出最多有多少點可以處在正確位置 Sample Input 5

1 1 2 5 4 Sample Output 3

解題方法： 我們先列一下普通的DP方程， dp[i]=max(dp[j]+1)(j<i,a[j]<a[i],a[i]?a[j]<=i?j) $$dp[i] = max(dp[j] + 1) (j < i, a[j] < a[i], a[i] - a[j] <= i - j)$$

然后這里就是3個限制條件了？CDQ三維偏序？翻了翻題解，發現神思路的題目。觀察三個限定條件。 1,j<i $$1, j < i$$ 2,a[j]<a[i] $$2,a[j] < a[i]$$ 3,a[i]?a[j]<=i?j $$3,a[i] - a[j] <= i - j$$

容易發現已知2,3可以推出1。 而1代表的是這n個數的排列順序。 而2的條件即為最長上升子序列。 所以我們不妨把3看做這n個數的重新排列法則，之后滿足2的條件即可。 所以我們只需要按照j?a[j]<=i?a[i]把n個數重新排列，接著求一個最長上升子序列長度即可。 需要注意的是，如果i?a[i]<0的話，那么顯然這個數不可能與C序列中的某個數對應上，直接跳過即可。

LIS可以二分也可以用樹狀數組的方法，PO爺用的樹狀數組的方法，可以看PO爺博客，蒟蒻寫了一個代碼和博主幾乎一樣的二分版本的代碼。