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

#include <bits/stdc++.h>
using namespace std;

class BuildingSelector {
private:
    const int MOD = 99997867;
    
    // 计算在范围内选择2个点的组合数
    long long calculateCombinations(int range) {
        if (range < 2) return 0;
        long long n = range;
        return (n * (n - 1)) / 2;
    }
    
public:
    int findValidCombinations(vector<int>& buildings, int maxDistance) {
        long long totalCombinations = 0;
        int leftPtr = 0;
        int n = buildings.size();
        
        // 使用双指针遍历所有可能的组合
        for (int rightPtr = 0; rightPtr < n; rightPtr++) {
            // 当距离超过限制时，移动左指针
            while (leftPtr < rightPtr && 
                   buildings[rightPtr] - buildings[leftPtr] > maxDistance) {
                leftPtr++;
            }
            
            // 计算当前窗口内的有效组合数
            if (rightPtr - leftPtr >= 2) {
                totalCombinations = (totalCombinations + 
                                   calculateCombinations(rightPtr - leftPtr)) % MOD;
            }
        }
        
        return static_cast<int>(totalCombinations);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int buildingCount, maxDistance;
    cin >> buildingCount >> maxDistance;
    
    vector<int> buildingPositions(buildingCount);
    for (int& pos : buildingPositions) {
        cin >> pos;
    }
    
    BuildingSelector selector;
    cout << selector.findValidCombinations(buildingPositions, maxDistance) << endl;
    
    return 0;
}

import java.util.*;

class BuildingSelector {
    private static final int MODULO = 99997867;
    
    // 计算有效范围内的组合数
    private long getValidCombinations(int range) {
        if (range < 2) return 0;
        long n = range;
        return (n * (n - 1)) / 2;
    }
    
    public int findPossiblePlans(int[] buildings, int maxDist) {
        long totalPlans = 0;
        int windowStart = 0;
        
        for (int windowEnd = 0; windowEnd < buildings.length; windowEnd++) {
            // 调整窗口起始位置
            while (windowStart < windowEnd && 
                   buildings[windowEnd] - buildings[windowStart] > maxDist) {
                windowStart++;
            }
            
            // 计算当前窗口内的可能方案数
            int windowSize = windowEnd - windowStart;
            if (windowSize >= 2) {
                totalPlans = (totalPlans + getValidCombinations(windowSize)) % MODULO;
            }
        }
        
        return (int) totalPlans;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int d = scanner.nextInt();
        
        int[] buildingPositions = new int[n];
        for (int i = 0; i < n; i++) {
            buildingPositions[i] = scanner.nextInt();
        }
        
        BuildingSelector selector = new BuildingSelector();
        System.out.println(selector.findPossiblePlans(buildingPositions, d));
        
        scanner.close();
    }
}

class BuildingSelector:
    def __init__(self):
        self.MODULO = 99997867
    
    def _calculate_combinations(self, window_size: int) -> int:
        """计算窗口内可能的组合数"""
        if window_size < 2:
            return 0
        return (window_size * (window_size - 1)) // 2
    
    def find_valid_plans(self, buildings: list, max_distance: int) -> int:
        """查找所有有效的埋伏方案数"""
        total_plans = 0
        left = 0
        n = len(buildings)
        
        # 使用滑动窗口查找有效组合
        for right in range(n):
            # 调整窗口左边界，确保最大距离不超过限制
            while left < right and buildings[right] - buildings[left] > max_distance:
                left += 1
            
            # 计算当前窗口内的有效方案数
            window_size = right - left
            if window_size >= 2:
                total_plans = (total_plans + self._calculate_combinations(window_size)) % self.MODULO
        
        return total_plans

def main():
    # 读取输入
    n, d = map(int, input().split())
    building_positions = list(map(int, input().split()))
    
    # 计算结果
    selector = BuildingSelector()
    result = selector.find_valid_plans(building_positions, d)
    print(result)

if __name__ == "__main__":
    main()