CF1485B Replace and Keep Sorted

给定一个正整数 $k$，如果两个数组满足以下条件，则称它们是 $k$-相似的： - 它们都是严格递增的； - 它们长度相同； - 它们的所有元素都是 $1$ 到 $k$（包含 $1$ 和 $k$）之间的正整数； - 它们恰好在一个位置上的元素不同。 现在给定一个整数 $k$、一个严格递增数组 $a$，以及 $q$ 个查询。对于每个查询，给定两个整数 $l_i \leq r_i$。你的任务是，对于每个查询，求有多少个数组 $b$ 满足 $b$ 与数组 $[a_{l_i},a_{l_i+1},\ldots,a_{r_i}]$ 是 $k$-相似的。

第一行包含三个整数 $n$、$q$ 和 $k$（$1\leq n, q \leq 10^5$，$n\leq k \leq 10^9$）——数组 $a$ 的长度、查询的数量和整数 $k$。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq k$）。该数组严格递增，即 $a_1 < a_2 < \ldots < a_n$。 接下来的 $q$ 行，每行包含两个整数 $l_i$、$r_i$（$1 \leq l_i \leq r_i \leq n$）。

输出 $q$ 行，第 $i$ 行输出第 $i$ 个查询的答案。

在第一个样例中： 对于第一个查询，有 $4$ 个数组与 $[2,4]$ 是 $5$-相似的：$[1,4]$、$[3,4]$、$[2,3]$、$[2,5]$。 对于第二个查询，有 $3$ 个数组与 $[4,5]$ 是 $5$-相似的：$[1,5]$、$[2,5]$、$[3,5]$。 由 ChatGPT 4.1 翻译