XKC's basketball team

  • 题意：给定一个序列，从每一个数后面比它大至少 \(ｍ\) 的数中求出与它之间最大的距离。如果没有则为 \(-1\)。

  • 题解：从后向前维护一个递增的队列，从后往前遍历，若当前的数大于队尾就进队，否则从该队列中二分找最小的比自己大至少 \(ｍ\) 的数，二者之间的距离即为答案。

  • 若当前数小于队尾，那这个数一定没有队尾的数优，因为它既比队尾的数靠前，又比它小。

  • 时间复杂度 \(O(nlogn)\) 。

  • 此题也可以用ST表+二分 等方法写出。

    标程（单调队列）：

#include <bits/stdc++.h>
using namespace std;
int a[500002], ans[500002];
vector<int> v, num;
int main() {
    int n,m;cin >> n>>m;
    for (int i = 1; i <= n; i++)cin >> a[i];
    v.clear(),num.clear();
    for (int i = n; i >= 1; i--) {
        if (v.size() == 0 || v.back() <a[i]) {
            v.push_back(a[i]);
            num.push_back(i);
            ans[i] = -1;
        } else {
            int j = (lower_bound(v.begin(), v.end(), a[i]+m) - v.begin());
            if(j==v.size())
                ans[i]=-1;
            else
                ans[i] = num[j] - i - 1;
        }
    }
    for (int i = 1; i < n; i++)
        cout << ans[i] << ' ';
    cout << ans[n] << endl;
    return 0;
}

居然大部分人用的是线段树，不过看上去确实是线段树水题。。。