题解 | #万万没想到之抓捕孔连顺#

#include <iostream>
#include <vector>
using namespace std;

class Solution2 {
public:
    int N, D;
    int mod = 99997867;
    vector<int> pos;
    Solution2(int _N, int _D, vector<int>& _pos) :N(_N), D(_D), pos(_pos) {}
    int biSearch(int lb, int rb, int target) {
        int l = lb - 1, r = rb + 1;
        while (l + 1 != r) {
            int m = (l + r) / 2;
            if (pos[m] <= target) {
                l = m;
            }
            else {
                r = m;
            }
        }
        return l;
    }
    int countPlan() {
        long long ret = 0;
        for (int i = 0; i < N - 2; i++) {
            int i2max = pos[i] + D;
            int i2 = biSearch(i, N - 1, i2max);
            long long dis = i2 - i;
            long long tmp = dis * (dis - 1) / 2;
            ret += tmp;
            ret %= mod;
        }
        return ret;
    }
};

int main() {
    int N = 0, D = 0;
    vector<int> pos;
    cin >> N >> D;
    int tmp = 0;
    for (int i = 0; i < N; i++) {
        cin >> tmp;
        pos.push_back(tmp);
    }
    Solution2 s(N, D, pos);
    cout << s.countPlan() << endl;
}