一道有思维难度的题

看题解看了好久才看懂的2333

怎么说呢，首先对于一个指针l，设最小满足条件的r为f[l]

易证得f[i]单调不减

然后就可以用两个指针扫了

l走的时候，r也一直走

然后需要维护l，r之间y的最大值最小值

这个用单调队列维护

然后就可以做完这题了

单调队列的题，思维难度都不小23333

还是有必要多写点这种题提高思维qwq

#include <bits/stdc++.h>
#define il inline
#define Max 1000005
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
using namespace std;
char In[Max],*tt=In,*ss=In;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,d,ans=0x3f3f3f3f,q1[Max],q2[Max],h1=1,t1,h2=1,t2;
struct node
{
    int x,y;
}e[Max];
il bool cmp(node a,node b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    else return a.y<b.y;
}
int main()
{
    n=read(),d=read();
    for(int i=1;i<=n;i++)
    {
        e[i].x=read(),e[i].y=read();
    }
    int r=0;
    sort(e+1,e+1+n,cmp);
    for(int l=1;l<=n;l++)
    {
        while(h1<=t1&&q1[h1]<l) h1++;
        while(h2<=t2&&q2[h2]<l) h2++;
        while(e[q1[h1]].y-e[q2[h2]].y<d&&r<n)
        {
            ++r;
            while(e[q1[t1]].y<e[r].y&&h1<=t1) t1--;
            while(e[q2[t2]].y>e[r].y&&h2<=t2) t2--;
            q1[++t1]=r;q2[++t2]=r;
        }
        if(e[q1[h1]].y-e[q2[h2]].y>=d) ans=min(ans,e[r].x-e[l].x);
    }
    if(ans>1000000000) puts("-1");
    else
        cout<<ans<<endl;
}