思路

发现这道题时一个 RMQ 区间求最值的题目，我们可以求出每个位置的左边 $D$ 包括的数的区间，和右边的区间，注意如果 $D = 4$，$5$ 和 $9$ 其实是在一个区间内的，然后可以算出区间最大值，再用这个最大值和 $2 \times h$ 去比较。

区间最值可以用 ST 表去做，也可以用单调队列去做。

代码

/*

 problem :
 by : ztrztr(luogu 602124)
 date : 2022/10/16
 update : 2022/10/16

*/
#include <bits/stdc++.h>
using namespace std;
int n, m, cnt;
int dp[100005][30];
struct node {
    int x, h;
} a[1000005];
int x[1000005];

bool cmp(node x, node y) {
    return x.x < y.x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;

    for (int i = 1; i <= n; i ++)
        cin >> a[i].x >> a[i].h;

    sort(a + 1, a + n + 1, cmp);

    for (int i = 1; i <= n; i ++)
        dp[i][0] = a[i].h, x[i] = a[i].x;

    for (int i = 1; i <= 21; i ++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j ++) {
            dp[j][i] = max(dp[j][i - 1], dp[j + (1 << (i - 1))][i - 1]);
        }
    }

    for (int i = 1; i <= n; i ++) {
        int l, r;
        l = lower_bound(x + 1, x + n + 1, a[i].x - m) - x;
        r = upper_bound(x + 1, x + n + 1, a[i].x + m) - x - 1;
        int c = log2(i - l + 1);
        int maxn = max(dp[l][c], dp[i - (1 << c) + 1][c]);
        c = log2(r - i + 1);
        int maxn2 = max(dp[i][c], dp[r - (1 << c) + 1][c]);
//      cout << l << " " << r << " " << a[i].x << " " << maxn << "\n";

        if (maxn >= 2 * a[i].h && maxn2 >= 2 * a[i].h)
            cnt ++;

    }

    cout << cnt;
    return 0;
}