问题分析

这是一个**最长严格上升子序列（LIS）**的变体问题。与经典LIS不同，我们可以：

1. 选择任意非空区间 $[l, r]$
2. 给这个区间的所有元素加上一个值 $d$，其中 $-x \le d \le x$
3. 目标是最大化修改后序列的LIS长度

关键观察

1. 修改区间的分类

修改区间 $[l, r]$ 与最终LIS的关系可以分为三种情况：

1. 情况1：LIS完全在修改区间左侧（$< l$）
2. 情况2：LIS完全在修改区间内部（$[l, r]$）
3. 情况3：LIS完全在修改区间右侧（$> r$）
4. 情况4：LIS横跨修改区间边界（需要重点处理）

2. 横跨边界的情况

这是本题的核心难点。对于LIS横跨 $[l, r]$ 边界的情况，可以进一步分为：

• 情况A：最后一个元素来自左侧，第一个元素来自右侧
• 情况B：最后一个元素来自内部，第一个元素来自右侧
• 情况C：最后一个元素来自左侧，第一个元素来自内部

3. 区间加减的影响

给区间 $[l, r]$ 所有元素加上 $d$，相当于：

• 区间内部元素：$t_i$ 变为 $t_i + d$
• 区间左侧元素：不变
• 区间右侧元素：不变

算法设计

1. 预处理前后缀LIS信息

对于每个位置 $i$，我们需要知道：

• $pre[i]$：以 $i$ 结尾的最长上升子序列长度（经典LIS）
• $suf[i]$：以 $i$ 开头的最长上升子序列长度

// 计算以每个位置结尾的LIS长度
vector<int> pre_lis(n);
vector<int> tails;  // tails[k] = 最小可能的末尾元素值，长度为k+1的LIS

for (int i = 0; i < n; i++) {
    auto it = lower_bound(tails.begin(), tails.end(), t[i]);
    pre_lis[i] = it - tails.begin();
    if (it == tails.end()) {
        tails.push_back(t[i]);
    } else {
        *it = t[i];
    }
}

// 计算以每个位置开头的LIS长度（反向处理）
vector<int> suf_lis(n);
tails.clear();
reverse(t.begin(), t.end());
for (int i = 0; i < n; i++) {
    // 注意：对于反向LIS，我们需要严格下降，所以用upper_bound并取反
    auto it = upper_bound(tails.begin(), tails.end(), -t[i]);
    suf_lis[n-1-i] = it - tails.begin();  // 注意索引映射
    if (it == tails.end()) {
        tails.push_back(-t[i]);
    } else {
        *it = -t[i];
    }
}

2. 考虑修改区间的影响

我们需要枚举修改区间 $[l, r]$ 并计算最优的 $d$ 值。

思路1：枚举分界点（$O(n^2)$，不可行）

对于每个可能的 $l, r$ 组合，重新计算LIS，显然太慢。

思路2：优化枚举（$O(n \log n)$）

观察发现，最优解通常出现在某些关键位置。我们可以：

1. 枚举分界点 $i$，假设LIS在 $i$ 处跨越修改边界
2. 分别计算左侧和右侧的最优解

3. 离散化处理

由于 $t_i$ 和 $d$ 的范围很大，我们需要离散化：

vector<int> all_values = t;
for (int val : t) {
    all_values.push_back(val - x);
    all_values.push_back(val + x);
}
sort(all_values.begin(), all_values.end());
all_values.erase(unique(all_values.begin(), all_values.end()), all_values.end());

4. 使用数据结构优化

对于每个位置 $i$，我们需要快速查询：

• 在 $i$ 左侧，以值 $< t_i + d$ 结尾的LIS的最大长度
• 在 $i$ 右侧，以值 $> t_i + d$ 开头的LIS的最大长度

可以使用线段树或树状数组维护。

完整算法

步骤1：预处理

1. 计算 $pre[i]$：以 $i$ 结尾的LIS长度
2. 计算 $suf[i]$：以 $i$ 开头的LIS长度
3. 离散化所有可能的值（原始值和加减x后的值）

步骤2：计算不修改的LIS

int original_lis = *max_element(pre.begin(), pre.end()) + 1;  // +1是因为pre[i]是0-based

步骤3：考虑LIS横跨修改边界的情况

这是最复杂的情况。我们需要找到一对 $(i, j)$，其中 $i < j$，且：

• $i$ 在修改区间内或左侧
• $j$ 在修改区间内或右侧
• 修改后 $t_i + \delta_i < t_j + \delta_j$（如果$i,j$在不同侧）

关键优化：分治思想

我们可以枚举中间的分界点 $k$，假设修改区间在 $k$ 的右侧：

int ans = original_lis;  // 至少是原始LIS

// 树状数组/线段树，用于维护最大值
FenwickTree left_tree(size), right_tree(size);

for (int k = 0; k < n; k++) {
    // 情况1：修改区间在k左侧，k在LIS中作为右侧部分
    int left_part = 0;
    // 查询左侧所有值 < t[k] - x 到 t[k] + x 范围内的最大pre值
    int left_val = query_left_tree(t[k] - x, t[k] + x);
    ans = max(ans, left_val + 1 + suf[k]);
    
    // 情况2：修改区间在k右侧，k在LIS中作为左侧部分
    int right_part = 0;
    // 查询右侧所有值 > t[k] - x 到 t[k] + x 范围内的最大suf值
    int right_val = query_right_tree(t[k] - x, t[k] + x);
    ans = max(ans, pre[k] + 1 + right_val);
    
    // 更新数据结构
    update_left_tree(t[k], pre[k]);
    update_right_tree(t[k], suf[k]);
}

步骤4：特殊情况处理

1. $x = 0$（子任务4）：直接返回原始LIS
2. $x$ 很大（子任务6）：相当于可以任意修改区间内的值

步骤5：最终答案

答案是所有情况的最大值。

时间复杂度分析

• 预处理前后缀LIS：$O(n \log n)$
• 离散化：$O(n \log n)$
• 主循环 + 数据结构查询：$O(n \log n)$
• 总复杂度：$O(n \log n)$

实现细节

数据结构设计

class FenwickTree {
private:
    vector<int> tree;
public:
    FenwickTree(int n) : tree(n + 2, 0) {}
    
    void update(int idx, int val) {
        idx++;  // 树状数组从1开始
        while (idx < tree.size()) {
            tree[idx] = max(tree[idx], val);
            idx += idx & -idx;
        }
    }
    
    int query(int idx) {
        idx++;  // 树状数组从1开始
        int res = 0;
        while (idx > 0) {
            res = max(res, tree[idx]);
            idx -= idx & -idx;
        }
        return res;
    }
};

处理大 $x$ 的情况

当 $x = 10^9$ 时，我们可以将区间内的值变得非常小或非常大：

• 最优策略：将整个区间设为极小值，然后连接左侧和右侧的LIS
• 答案可能是：$pre[l-1] + (r-l+1) + suf[r+1]$

样例解析

输入：

n=8, x=10
t = [7, 3, 5, 12, 2, 7, 3, 4]

原始LIS：[3, 5, 7] 或 [2, 3, 4]，长度为3

修改方案：

• 选择区间 $[2,3]$（1-based索引，对应值 3,5）
• 加上 $d=-5$
• 新序列：[7, -2, 0, 12, 2, 7, 3, 4]
• 新LIS：[-2, 0, 2, 3, 4]，长度为5

总结

本题的核心思路：

1. 分解问题：将修改区间与LIS的位置关系分类讨论
2. 预处理：计算前后缀LIS信息
3. 数据结构优化：使用树状数组/线段树快速查询最优值
4. 离散化：处理大范围的值域

关键难点：

1. 理解LIS如何横跨修改区间边界
2. 设计高效的数据结构查询
3. 处理边界情况和特殊约束

最终算法：

• 时间复杂度：$O(n \log n)$
• 空间复杂度：$O(n)$