The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

Problem links: (CF, Luogu) | I strongly recommend reading it on the blog.

The first CF Div. 4 I participated in.

This problem is the kind that becomes very, very simple once you think of the key point, but if you do not, then… you are done for (~~I was one of those who were done for~~).

1. Problem Statement:

Given an array $a$ of length $n \ (\sum n < 2\cdot 10^5)$ , find how many intervals of length $k + 1 \ (1\le k < n)$ in the array satisfy the following condition:

$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{Note: i is the starting position of this interval.}$

2. Approach

Brute force is still easy to implement: just calculate every possible interval in the array. However, seeing the condition $\sum n < 2\cdot 10^5$ tells us that this will not work.

Therefore, we need a method that can determine whether an interval satisfies the condition in $O(1)$ time. (If you can produce an $O(\log n)$ method, that is also acceptable.)

We can see that brute force is needed because the starting position of the interval changes each time, so the number by which each item of the array must be multiplied is uncertain. But if we can find a condition independent of the interval’s starting position, the problem is solved.

Next comes the key point.

Looking more carefully at the condition given in the problem, we can see that, for the condition to hold, the preceding item in the array must be less than twice the following item, namely:

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

This property is independent of the position and length of the interval. As long as two adjacent numbers satisfy this condition, they can appear in an interval of any length and at any position.

However, these are only two numbers in the interval. If we want an entire interval to be valid, we need every $a_i$ in the interval to be less than $2\cdot a_{i+1}$ .

In other words, as long as an interval of length $k$ contains $k - 1$ pairs satisfying $a_i < 2 \cdot a_{i + 1}$ , the interval satisfies the condition.

Counting the number of valid pairs in an interval… and querying the result in $O(1)$ time—is that not exactly a prefix sum?

Therefore, after determining whether each pair is valid, we naturally create a prefix-sum array valid_sum[i] to count how many valid pairs there are up to $i$ .

Finally, we use another loop to count the valid intervals.

3. Code:

The code is fairly simple. The point $a_i < 2 \cdot a_{i + 1}$ is still relatively difficult to think of in this problem.

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        int n, k;
        scanf("%d%d", &n, &k);
        // Note that the problem gives you k, but the actual length of this interval is 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;
                // Determine and record whether the pair a[i] and a[i + 1] is valid.
            }
            valid_sum[i] = valid_sum[i - 1] + valid[i];
            // Prefix sum.
        }
        int ans = 0;
        for(int i = 1; i <= n - k; i++){
            if(valid_sum[i + k - 1] - valid_sum[i - 1] == k){
                // The actual length is k + 1, so k + 1 minus 1 equals k.
                ans++;
            }
        }

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