[USACO12MAR]花盆 二分 单调队列

存在一个长度为\(x\)的区间\([l,r]\)，使得区间中最大值与最小值差至少为\(w\)，求这个最小的\(x\)

\(n\le 100000\)，\(w\le 1000000\)

显然区间长度\(x\)越大，最值之差越大，满足单调性，上二分答案，问题转化为是否存在长度为\(mid\)的区间中最值之差至少为\(w\)，而这个问题可以用单调队列（滑动窗口）\(O(n)\)解决。

单调队列存的下标，首先判断队首是否合法（窗口大小），然后按照“比你强还比你年轻”的原则弹队尾维护队列即可。

#include <cstdio>

#include <algorithm>

#define MAXN 100010

using namespace std;

int n,d;

struct nod{

    int x,y;

    const bool operator < (const nod &a) const{

        return x<a.x;

    }

} a[MAXN];

namespace quemx {

    int q[MAXN],head,tail;

}

namespace quemin {

    int q[MAXN],head,tail;

}

inline bool check(int wid) {

    quemx::head=1,quemx::tail=0;

    quemin::head=1,quemin::tail=0;

    for(int i=1;i<=n;++i){

        // 滑动窗口宽度

        while(quemx::head<=quemx::tail&&a[i].x-a[quemx::q[quemx::head]].x>wid) ++quemx::head;

        while(quemin::head<=quemin::tail&&a[i].x-a[quemin::q[quemin::head]].x>wid) ++quemin::head;

        // 维护单调队列

        while(quemx::head<=quemx::tail&&a[quemx::q[quemx::tail]].y<=a[i].y) --quemx::tail;

        while(quemin::head<=quemin::tail&&a[quemin::q[quemin::tail]].y>=a[i].y) --quemin::tail;

        // 入队

        quemx::q[++quemx::tail]=i;

        quemin::q[++quemin::tail]=i;

        if(a[quemx::q[quemx::head]].y-a[quemin::q[quemin::head]].y>=d) return 1;

    }

    return 0;

}

int main() {

    scanf("%d %d", &n, &d);

    int l=1,r=0;

    for(int i=1;i<=n;++i) scanf("%d%d", &a[i].x, &a[i].y), r=max(r, a[i].x);

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

    int ans=-1;

    while(l<=r){

        int mid=(l+r)>>1;

        if(check(mid)) r=mid-1, ans=mid;

        else l=mid+1;

    }

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

    return 0;

}