问题理解

JOI超市有 $N$ 天的销售额数据 $A_1, A_2, \ldots, A_N$。我们需要选择一组天数 $p_1 < p_2 < \cdots < p_m$ 展示，满足：

1. 必须包含最后一天：$p_m = N$
2. 相邻两天间隔不超过 $D$：$p_{j+1} - p_j \le D$（对 $1 \le j < m$）

目标是最大化印象分——选中的天数中，销售额是前缀最大值的天数数量。

---

关键观察

1. 问题结构

• 这是一个序列上的最长上升子序列（LIS）变种问题
• 增加了两个约束：
  • 必须包含最后一天 $N$
  • 相邻选中天数间隔不超过 $D$
• 印象分实际上就是选中序列的严格递增子序列长度

2. 约束条件的转化

• 条件2（相邻间隔 ≤ $D$）可以理解为：对于每个位置 $i$，它的前驱只能来自 $[i-D, i-1]$ 区间
• 条件1（必须包含 $N$）意味着我们最终需要计算以 $N$ 结尾的最优解

3. 动态规划思路

定义 $dp[i]$ 表示以第 $i$ 天结尾，且满足间隔约束的最大印象分。则有：

$$dp[i] = 1 + \max_{j \in [i-D, i-1], \ A_j < A_i} dp[j] $$

其中 $j$ 需要满足 $A_j < A_i$（严格递增），且位置在 $i$ 之前最多 $D$ 天内。

---

算法设计

1. 朴素动态规划

直接按照上述递推式计算，时间复杂度为 $O(N^2)$，无法通过 $N \le 3\times 10^5$ 的数据。

2. 优化思路

我们需要快速查询：

• 在区间 $[i-D, i-1]$ 中
• 所有满足 $A_j < A_i$ 的位置 $j$
• 的最大 $dp$ 值

这是一个二维偏序查询问题，可以使用数据结构优化。

3. 离散化与排序

• 首先将销售额 $A_i$ 离散化（因为 $A_i$ 范围较大）
• 按 $A_i$ 从小到大处理每个位置，相同 $A_i$ 按位置从大到小处理（避免相同值之间的转移）

4. 数据结构选择

• 线段树：维护位置区间 $[1, N]$ 的最大 $dp$ 值
• 并查集：辅助跳过已处理的位置，优化查询范围

5. 算法流程

1. 将 $(A_i, i)$ 按 $A_i$ 升序、$i$ 降序排序
2. 初始化线段树，所有位置 $dp$ 值为 $0$
3. 按排序顺序处理每个位置 $i$：
   • 在 $[i-D, i-1]$ 区间内查询最大 $dp$ 值
   • $dp[i] = \text{查询结果} + 1$
   • 将位置 $i$ 的 $dp$ 值更新为 $dp[i]$
4. 最终答案为 $dp[N]$

6. 查询优化技巧

使用并查集维护已处理的位置：

• 对于每个位置 $i$，找到 $[i-D, i-1]$ 中第一个已处理的位置
• 通过并查集快速跳过连续已处理的区间
• 将查询范围缩小到实际可能转移的位置

---

算法正确性

1. 排序处理的正确性

• 按 $A_i$ 升序处理确保了只从值更小的位置转移
• 相同值按位置降序处理避免了相同值之间的非法转移

2. 区间查询的完备性

• 并查集确保了查询区间内所有可能的前驱位置都被考虑
• 线段树保证了在合法区间内找到最大 $dp$ 值

3. 约束条件的满足

• 查询区间 $[i-D, i-1]$ 保证了相邻间隔约束
• 最终答案 $dp[N]$ 保证了必须包含最后一天

---

复杂度分析

时间复杂度

• 排序：$O(N \log N)$
• 每个位置处理：
  • 并查集查找：近似 $O(\alpha(N))$
  • 线段树查询/更新：$O(\log N)$
• 总复杂度：$O(N \log N)$

空间复杂度

• 存储 $A_i$ 和 $dp$ 值：$O(N)$
• 线段树：$O(N)$
• 并查集：$O(N)$
• 总复杂度：$O(N)$

---

代码实现要点

1. 数据结构定义

struct Element {
    int id, a;  // 位置，销售额
} e[N];

bool cmp(Element x, Element y) {
    if (x.a == y.a) return x.id > y.id;
    return x.a < y.a;
}

int t[N << 2];  // 线段树
int fa[N];      // 并查集
int dp[N];      // DP数组

2. 线段树操作

• modify(): 单点更新 $dp$ 值
• query(): 区间查询最大 $dp$ 值
• queryr(): 查找区间内第一个非零位置

3. 并查集优化

int find(int x) {
    if (fa[x] == x) {
        int pos = queryr(1, 1, n, max(x - d, 1));
        if (pos <= x - 1) fa[x] = find(pos);
        return fa[x];
    }
    return fa[x] = find(fa[x]);
}

4. 主算法流程

1. 读取输入并离散化
2. 按规则排序
3. 初始化数据结构
4. 按排序顺序处理每个位置
5. 输出 $dp[N]$（即线段树根节点）

---

算法标签

• 动态规划
• 线段树/树状数组
• 并查集
• 最长上升子序列

---

总结

本题通过将原问题转化为带约束的LIS问题，并利用数据结构优化转移过程。关键点在于：

1. 按值排序处理，将二维偏序问题降为一维区间查询
2. 使用线段树维护区间最大 $dp$ 值
3. 通过并查集优化查询区间，快速定位可转移的前驱位置

算法在 $O(N \log N)$ 时间内解决了问题，可以处理 $N \le 3\times 10^5$ 的大数据规模。