1. 题意：

给你一个长度为 $n \ (\sum n < 2\cdot 10^5)$ 的数组 $a$ ，问你在这个数组中，有多少个长度为 $k + 1 \ (1\le k < n)$ 的区间，符合以下的条件：

$2^0 \cdot a_i < 2^1 \cdot a_{i + 1} < 2^2 \cdot a_{i + 2} < \dotsi < 2^k \cdot a_{i + k}\\ \footnotesize{注：i 为这个区间开始的位置}$

2. 思路

暴力还是很好搞的，就把数组中每个可能的区间都算一遍就行了，但是看到 $\sum n < 2\cdot 10^5$ 这个条件就知道要寄了。

所以我们需要一种能在 $O(1)$ 的时间内判断区间是否符合条件的方法。（你要能搞出来 $O(\log n)$ 的也不是不可以）

可以发现，采用暴力的方法是因为每次这个区间的起始位都会变，所以数组的每一项前面要乘的数都不确定的。但如果我们能找到一种跟区间起始位置不相关的判断条件，这个问题就解决了。

接下来，重点来了

再仔细观察题目中给的条件，可以发现如果想要符合条件，数组中的前一项必须小于后一项的两倍，也就是：

$a_i < 2 \cdot a_{i + 1}$

这个性质是和区间的位置，以及长度不相关的，只要两个相邻的数符合这个条件，那么它可以出现在任何长度，位置的区间中。

不过，这只是区间中的两个数，如果我们想要让一整个区间都合法，那么我们就需要让整个区间内，任意的 $a_i$ 都小于 $2\cdot a_{i+ 1}$ 。

也就是说，只要长度为 $k$ 的区间内，有 $k - 1$ 个符合 $a_i < 2 \cdot a_{i + 1}$ 的数对，那这个区间就是符合条件的。

统计区间内的合法数量……并且需要在 $O(1)$ 的时间内查询到结果，那这不就是前缀和吗？

于是我们很自然的就想到了判断完每个数对是否合法后，开一个前缀和数组 valid_sum[i] 来统计，到 $i$ 为止，有多少个符合条件的数对。

最后再搞个循环统计一下符合条件的区间就好了。

3. 代码：

代码还是比较简单的，这题的 $a_i < 2 \cdot a_{i + 1}$ 这个点还是比较难想。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        int n, k;
        scanf("%d%d", &n, &k);
        //注意他给你的是 k，但是这个区间实际的长度是 k + 1
        int a[n + 1];
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
        }
        bool valid[n + 1];
        memset(valid, 0, sizeof(valid));
        int valid_sum[n + 1];
        memset(valid_sum, 0, sizeof(valid_sum));

        for(int i = 1; i < n; i++){
            if(a[i] < 2 * a[i + 1]){
                valid[i] = true;
                //判断和记录 a[i] 和 a[i + 1] 这个树对是否合法。
            }
            valid_sum[i] = valid_sum[i - 1] + valid[i];
            //前缀和
        }
        int ans = 0;
        for(int i = 1; i <= n - k; i++){
            if(valid_sum[i + k - 1] - valid_sum[i - 1] == k){
                //实际长度是 k + 1，所以 k + 1 再 - 1 = k
                ans++;
            }
        }

        printf("%d\n", ans);
    }
}