UNR 2025 D2T1

有点 ATCoder 劲的计数题。快速通过这个题、给 T2 留出时间是在 Day 2 取得高分的基石。

首先尝试观察合法解的结构。可以把 $+k$ 移项，变成 $p_{i} - k > p_{j}$ 且 $p_{j} - k > p_{i}$。下面记 $q_{i} = p_{i} - k$。假设 $i < j$，那么 $q_{i} > j$ 的一个必要条件是 $q_{i} > i$。我们可以感受到满足 $q_{i} > i$ 的位置是关键的，考虑先取出这些位置，分析剩下空位的结构。

考察相邻两个关键位置 $i$ 和 $i'$。显然不能有 $q_{i} > i'$，否则二元组 $(i, i')$ 不合法。设 $q_i = x \in [i + 1, i' - 1]$，那么中间这段区间被分成了两段：左边的 $[i + 1, x - 1]$ 必须满足 $q_j \le i$，而右边的 $[x, i' - 1]$ 必须满足 $q_j \le j$。画图容易发现这个条件是充要的。因此我们发现一个性质：填到关键位置 $i$ 的时候，除了 $q_i$ 本身，用的都是 $\le i$ 的数。这个性质给了我们 dp 计数的机会。

考虑设 $f_i$ 表示目前已经走到 $i$，填完了 $[1, i - 1]$ 的所有 $q$，合法的方案数是多少。转移时枚举下一个关键位置 $i'$，以及 $q_i = x$。分别计算两个区间的方案数：第一个区间相当于把 $\le i$ 的未填数（这里由于 $[1, i - 1]$ 填的都是 $\le i$ 的，消耗掉的数量可以 $\mathcal O(1)$ 前缀和计算），第二个区间相当于从小到大确定每个数的填法，最后乘起来。

暴力做时间复杂度 $\mathcal O(n^3) \sim \mathcal O(n ^4)$ 不等。优化的方法也很容易：考虑扫描线，扫描 $i'$ 的同时维护所有决策的系数之和，系数变化无非是乘上一个数，清零，或者加入一个数。直接 $\mathcal O(1)$ 维护变化就行了，复杂度 $\mathcal O(n ^ 2)$。