K-Good 子序列 - 题目

Busy Beaver 太懒了，不想为这个问题写一个有趣的故事，所以他直接给出了形式化的描述。

定义一个 $M$-序列 为一个由正整数组成的序列，其中每个元素都在 $1$ 到 $M$ 之间（包含 $1$ 和 $M$）。

如果一个 $M$-序列中任意一对相邻元素的绝对差值都不超过 $K$，则称该序列为 $K$-好 的。例如，$[1, 2, 3, 5, 5, 3, 2, 1]$ 是 $2$-好且 $2024$-好的，但不是 $1$-好的。我们认为长度为 $0$ 或 $1$ 的 $M$-序列也是 $K$-好的。

给定正整数 $N, M, K, L$ 以及一个长度为 $N$ 的 $M$-序列 $a_1, \dots, a_N$，求一个 $M$-序列 $b$ 的最大可能长度，使得：

回想一下，序列的子序列是通过从原序列中删除若干元素（可能全部删除或不删除）得到的，且不改变剩余元素的相对顺序。

输入包含多个测试用例。第一行包含一个正整数 $T$ ($1 \le T \le 2 \cdot 10^5$)，表示测试用例的数量。

每个测试用例的第一行包含四个整数 $N, M, K, L$ ($0 \le N \le 2 \cdot 10^5$, $1 \le M \le 10^9$, $0 \le K \le 10^9$, $1 \le L \le 10^9$)。

每个测试用例的第二行包含 $a_1, \dots, a_N$ ($1 \le a_i \le M$)。如果 $N = 0$，则跳过此行。

保证 $a$ 的每一个 $K$-好子序列的长度都不超过 $L$。此外，所有测试用例的 $N$ 之和不超过 $4 \cdot 10^5$。

对于每个测试用例，输出一行，表示 $b$ 的最大长度。可以证明，在题目给定的约束条件下，最大值总是存在的且不超过 $9 \cdot 10^{18}$。

3
3 3 1 3
1 3 2
0 5 2 3
7 7 2 3
1 4 2 7 7 1 6

5
6
7

在第一个样例测试用例中，一个可能的 $M$-序列 $b$ 是 $[1, 3, 2, 3, 1]$，其 $1$-好子序列（如 $[3, 2, 3]$ 和 $[3, 2, 1]$）的长度均不超过 $L = 3$。

在第二个样例测试用例中，一个可能的 $M$-序列 $b$ 是 $[1, 1, 5, 4, 2, 5]$，其 $2$-好子序列（如 $[5, 4, 2]$ 和 $[1, 1, 2]$）的长度均不超过 $L = 3$。

在第三个样例测试用例中，可以证明唯一的可能序列 $b$ 即为 $b = a$。

QOJ.ac