CF1692G 2^Sort

给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$，请你求出有多少个下标 $1 \leq i \leq n - k$，使得长度为 $k+1$ 的子数组 $[a_i, \dots, a_{i+k}]$（注意长度为 $k+1$，不是 $k$）满足以下性质： - 如果将第一个元素乘以 $2^0$，第二个元素乘以 $2^1$，……，第 $k+1$ 个元素乘以 $2^k$，那么这个子数组是严格递增的。 更正式地说，统计有多少个下标 $1 \leq i \leq n - k$ 满足 $$ 2^0 \cdot a_i < 2^1 \cdot a_{i+1} < 2^2 \cdot a_{i+2} < \dots < 2^k \cdot a_{i+k}。 $$

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$3 \leq n \leq 2 \times 10^5$，$1 \leq k < n$），分别表示数组的长度和不等式的数量。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），表示数组的元素。 所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示满足题目条件的下标数量。

在第一个测试用例中，两个子数组都满足条件： - $i=1$：子数组 $[a_1,a_2,a_3] = [20,22,19]$，有 $1 \cdot 20 < 2 \cdot 22 < 4 \cdot 19$。 - $i=2$：子数组 $[a_2,a_3,a_4] = [22,19,84]$，有 $1 \cdot 22 < 2 \cdot 19 < 4 \cdot 84$。 在第二个测试用例中，有三个子数组满足条件： - $i=1$：子数组 $[a_1,a_2] = [9,5]$，有 $1 \cdot 9 < 2 \cdot 5$。 - $i=2$：子数组 $[a_2,a_3] = [5,3]$，有 $1 \cdot 5 < 2 \cdot 3$。 - $i=3$：子数组 $[a_3,a_4] = [3,2]$，有 $1 \cdot 3 < 2 \cdot 2$。 - $i=4$：子数组 $[a_4,a_5] = [2,1]$，但 $1 \cdot 2 = 2 \cdot 1$，所以这个子数组不满足条件。 由 ChatGPT 4.1 翻译