📌 二分优化 LIS

---

二分优化 LIS

🔍 核心思路：维护一个「结尾尽可能小」的上升子序列

我们使用一个辅助数组 d[]，来帮助我们记录不同长度的上升子序列的“最小结尾值”。这个数组始终保持单调递增。

---

🛠️ 更新规则说明

1. 初始化

   • 定义一个变量 len = 0，表示当前找到的最长上升子序列的长度。
   • 定义数组 d[]，用于记录每个长度的上升子序列的最小结尾值。

2. 遍历数组中的每个元素 a[i]，对于每一个 a[i]，我们有两种情况：

   • 情况一：a[i] 大于 d[len]
     说明 a[i] 可以接在当前最长的上升子序列后面。
     👉 直接扩展序列：d[++len] = a[i]。

   • 情况二：a[i] 无法接在末尾
     我们需要在 d[1...len] 中找到一个最大的 $j$ 使得 $d[j]\leq a[i]$，那么 $a[i]$ 就成功拼到了 $j$ 的后面，即更新 $d[j+1]\gets a[i]$ 👉 换言之：$d[j+1]$ 是满足恰好大于等于 $a[i]$ 的位置。

   这样做的目的是：

   • 替换成更小的结尾值，有利于后续拼接更多更大的元素。
   • 保证数组 d[] 仍然单调递增。

---

💡 为什么这样可以？

• 辅助数组 d[] 中，d[i] 表示长度为 i 的上升子序列中结尾元素的最小值。
• 替换 d[pos] 并不会改变原本的子序列长度，只是让这个子序列的结尾更小，更容易接上新的元素。
• 我们始终保持 d[] 单调递增：d[1] < d[2] < ... < d[len]

---

📘 示例

以 a = [3, 1, 2, 4] 为例：

遍历元素	更新方式	d[] 状态
3	新增：len = 1	[3]
1	替换位置1	[1]
2	新增：len = 2	[1, 2]
4	新增：len = 3	[1, 2, 4]

最终的 d[] = [1, 2, 4]，所以最长上升子序列长度为 3。

---

✅ C++ 示例代码

for (int i = 1; i <= n; i++) 
{
    if (a[i] > d[len]) // 严格大于
    {
        d[++len] = a[i];
        f[i] = len;
    } 
    else 
    {
        int pos = lower_bound(d + 1, d + len + 1, a[i]) - d;
        d[pos] = a[i];
        f[i] = pos;
    }
}

---

📈 拓展变形问题

---

除了「最长严格上升子序列」（LIS）之外，我们还可以通过类似的方法解决其它变形问题。核心思路相同：用辅助数组 d[] 维护不同长度子序列的最优结尾值，只需根据要求调整比较规则。

---

1️⃣ 最长不下降子序列

🔸 特点：后一个数可以等于前一个数
🔸 判断条件和更新逻辑：

• 如果 a[i] >= d[len]：说明可以继续接在末尾
  👉 d[++len] = a[i]

• 否则：使用 upper_bound 找到第一个大于 a[i] 的位置 pos，用 a[i] 去更新 d[pos]
  👉 d[pos] = a[i]
  ⚠️ 注意：不要替换等于的元素，保持不下降的关系

for (int i = 1; i <= n; i++) 
{
    if (a[i] >= d[len])  // 大于或等于最后一个即可
    {
        d[++len] = a[i];
        f[i] = len;
    } 
    else 
    {
        int pos = upper_bound(d + 1, d + len + 1, a[i]) - d;
        d[pos] = a[i];
        f[i] = pos;
    }
}

---

2️⃣ 最长下降子序列

🔸 d[]：为了下降长度更长，此时 d[i] 维护长度为 $i$ 结尾的 最大值。有利于后续元素拼接 🔸 特点：后一个数必须严格小于前一个数
🔸 判断条件和更新逻辑：

• 如果 a[i] < d[len]：说明可以接在末尾
  👉 d[++len] = a[i]

• 否则：使用自定义的二分查找，找到第一个小于等于 a[i] 的位置 pos，然后更新
  👉 d[pos] = a[i]

⚠：注意初始化 d[0] = 1e9 保证 $a[1] < d[0]$ 成立。

d[0] = 1e9; // 初始化大一些，根据数据范围自己判定。
for (int i = 1; i <= n; i++) 
{
    if (a[i] < d[len]) // 严格小于
    {
        d[++len] = a[i];
        f[i] = len;
    } 
    else 
    {
        int l = 1, r = len, pos = 0;
        while (l <= r) 
        {
            int mid = (l + r) >> 1;
            if (d[mid] <= a[i]) pos = mid, r = mid - 1;
            else l = mid + 1;
        }
        d[pos] = a[i];
        f[i] = pos;
    }
}

---

3️⃣ 最长不上升子序列

🔸 特点：后一个数可以等于或小于前一个数
🔸 判断条件和更新逻辑：

• 如果 a[i] <= d[len]：说明可以接在末尾
  👉 d[++len] = a[i]

• 否则：使用自定义的二分查找，找到第一个小于 a[i] 的位置 pos，然后更新
  👉 d[pos] = a[i]

⚠：注意初始化 d[0] = 1e9 保证 $a[1] < d[0]$ 成立。

d[0] = 1e9; // 初始化大一些，根据数据范围自己判定。
for (int i = 1; i <= n; i++) 
{
    if (a[i] <= d[len]) // 小于或等于均可
    {
        d[++len] = a[i];
        f[i] = len;
    } 
    else 
    {
        int l = 1, r = len, pos = 0;
        while (l <= r) 
        {
            int mid = (l + r) >> 1;
            if (d[mid] < a[i]) pos = mid, r = mid - 1;
            else l = mid + 1;
        }
        d[pos] = a[i];
        f[i] = pos;
    }
}

---

✅ 小结对比

类型	接在末尾的条件	查找方式（替换）
严格上升子序列	a[i] > d[len]	lower_bound ≥ a[i]
不下降子序列	a[i] >= d[len]	upper_bound > a[i]
严格下降子序列	a[i] < d[len]	自定义二分：<= a[i]
不上升子序列	a[i] <= d[len]	自定义二分：< a[i]

以上每种情况都可以在 $O(n \log n)$ 的时间内解决，核心在于维护 d[] 的结构和选择正确的查找方式。

---