Acwing.896 最长上升子序列Ⅱ

个人疑惑问题的记录和解答(如有错误希望佬们能指正一下)

问题一：为什么二分的时候左右边界分别是l = 0, r = len?

看到一个佬说的一句话很好，放在问题解答的开头：右二分，左溢出。用0揽住a[i]比q[1]小的情况。

因为二分的时候我们是对q[]进行二分查找，而q[i]的含义是长度为i的单调递增子序列的最后一个元素的最小
值，所以长度len = 0时，无需查找，因为长度为0的单调递增子序列的最后一个元素并不存在，len = 1时，
我们二分的区间理论上应该是[1~1]，len = 2时，二分区间理论上是[1~2]依此类推(即[1~len])，那么为什么
二分的区间代码实现需要写成[0~len]？如果不写成[0~len]，我将其展开写应该是写成如下代码

    int len = 1; // len = 0无意义直接从1开始
    q[1] = a[0]; // 最开始的时候长度为一的子序列长度很显然是a[0]一个元素组成，直接初始化
    for (int i = 1; i < n; i ++ ){ // 此处因为a[0]已经初始化了，直接从1开始即可
        int l = 1, r = len; 
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }

        二分查找到q[1]时可能有两种情况:
        情况一：q[1]就是q[]中比a[i]小的最大值
        情况二：q[1]不是比a[i]小的最大值，q[]中不存在严格比a[i]小的值
        对于情况一，我们应该将a[i]放在q[1]后面形成len = 2的子序列，并更新q[2]的值
        对于情况二，我们直接更新q[1]的值为a[i]即可

        除此之外的情况，查找到q[1]以后的位置均是因为查找到了正确的结果

        if (l == 1 && q[l] >= a[i]) { 
        q[l] = a[i];
        }
        else if (l == 1 && q[l] < a[i]){
            len = max(len, l + 1);
            q[l + 1] = a[i];
        }
        else {
            len = max(len, l + 1);
            q[l + 1] = a[i];
        }
    }

如果我们将二分的区间写成[0~len]就无须如此分类，因为如果我们要查询的值不在[1~len]之间，二分查找的
结果必然是q[0](对本题是这样，因为本题中q[]严格单增，而且因为如果不存在想要的结果查找的结果必然
是q[0]，所以y总讲解中将q[0]置为-2e9当作哨兵存在理论意义，不具备实际意义，实际代码中可不写，
**对本题是如此**)查找到q[0](即l = r = 0)后，直接用 
        len = max(len, l + 1); 
        q[l + 1] = a[i];
就可以正确的更新所有的情况，即如下代码：

    int len = 1;
    q[1] = a[0]
    for (int i = 1; i < n; i ++ ){
        int l = 0, r = len; 
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, l + 1);
        q[l + 1] = a[i];
    }

我们观察可知，len = i = 0 时候是刚开始访问a[]，此时不满足二分的条件，不会进入二分，直接会直接更
新q[1] = a[0]，如此看来该代码可以再精简一下省去手动初始化q[1]的过程得到最终结果如下：

    int len = 0;
    for (int i = 0; i < n; i ++ ){
        int l = 0, r = len; 
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, l + 1);
        q[l + 1] = a[i];
    }

问题二：对q[1~len]遍历后输出的结果是不是单调递增子序列？

并不是，q中的数据不断被a[i]更新，q[1~len]的结果甚至不一定是子序列
如：
2 3 1
计算后，q[1~len] = [1, 3]

问题三：q[l + 1] = a[i]的证明 (相同长度的单调递增子序列，后得到的子序列的最后一个数的数值一定小于等于先得到的子序列)

假设长度相同的两个子序列分别是xxxa和xxxb, 先得到的子序列是xxxa,后得到的是xxxb，如果b > a, 那么b
就可以接在xxxa后面形成xxxab，长度增加，与假设矛盾，故b ≤ a，得证。

问题四：q[]数组的长度len为什么是最长单调递增子序列长度？

这与q[]的更新过程相关联，明白了更新的过程就可以明白为什么。
我们不断遍历a[]中的数，并在q[]中不断寻找小于a[i]且最接近a[i]的数，如果这个数存在，那么a[i]可以放
在这个数后面形成一个更长的严格递增子序列(即len = max(len, l + 1); q[l + 1] = a[i])，如果不存在，
则说明a[i]自己只能形成长度为1的单调递增子序列，更新一下q[1] = a[i]。这样操作下来，q[]数组的长度就
是在遍历a[]的过程中更新过的q[]的所有位置，而q[i]的含义就代表了单调递增子序列的长度，所以len就是最
长单增子序列长度

问题五：该题解法与单调队列，单调栈的区别

单调队列是将所有大于新加入元素的元素全部出队，然后队尾加入新元素，来保证单调性；而本题是将新加入
的元素替换数组中大于等于它的第一个元素，确保遍历完成后q[]的长度就是最大上升子序列长度

完整代码如下：

#include <iostream>

using namespace std;

const int N = 100010;

int a[N], q[N]; // q[i]的含义是长度为i的单调递增子序列的最后一个元素的最小值
int n;

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        scanf("%d", &a[i]);

    int len = 0;
    for (int i = 0; i < n; i ++ ){
        int l = 0, r = len; 
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, l + 1);
        q[l + 1] = a[i];
    }

    printf("%d", len);
    return 0;
}