[USACO12MAR]花盆（单调队列）

题意

有n个点\((x,y)\)，求一个在\(x\)轴上的最小区间，使得它包含的所有点中的\(y\)的极差至少为\(d\)，\(x,y,d\leq 10^6\)

思路

将点按\(x\)排序，显然\(2-pointers\)，需要随时维护一个滑动窗口的最大值和最小值，显然单调队列（也可以用离散化+ST表或者线段树，不过多了个log）

Code

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,d,ans=N*1000;
int qmax[N],lmax,rmax;
int qmin[N],lmin,rmin;
struct Node { int x,y; } nd[N];

template <class T>
void read(T &x)
{
    char c;int sign=1;
    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
bool cmp(Node a,Node b) { return a.x<b.x; }
int main()
{
    read(n);read(d);
    for(int i=1;i<=n;++i) read(nd[i].x),read(nd[i].y);
    sort(nd+1,nd+n+1,cmp);
    lmax=lmin=1;
    rmax=rmin=0;
    int now=0;
    for(int i=1;i<=n;++i)
    {
        while(lmax<=rmax && qmax[lmax]<i) ++lmax;
        while(lmin<=rmin && qmin[lmin]<i) ++lmin;
        while(now<n&&nd[qmax[lmax]].y-nd[qmin[lmin]].y<d)
        {
            ++now;
            while(lmax<=rmax && nd[qmax[rmax]].y<nd[now].y) --rmax;
            while(lmin<=rmin && nd[qmin[rmin]].y>nd[now].y) --rmin;
            qmax[++rmax]=now;
            qmin[++rmin]=now;
        }
//      cout<<nd[qmax[lmax]].y<<' '<<nd[qmin[lmin]].y<<endl;
        if(nd[qmax[lmax]].y-nd[qmin[lmin]].y>=d) ans=min(ans,nd[now].x-nd[i].x);
    }
    if(ans==N*1000) cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}

[USACO12MAR]花盆（单调队列）

原文：https://www.cnblogs.com/Chtholly/p/11672708.html