题解 P2698 【[USACO12MAR]花盆Flowerpot】

先安利一下自己的博客 [YoungNeal](http://www.cnblogs.com/YoungNeal/) 虽然这题是从单调队列标签里找出来的，但是由于太菜，一直想不到怎样用单调队列解决这题。 所以蒟蒻的我用了 ST表 先科普一下 ST表：对于一个数列，在 $O(nlogn)$ 的时间里预处理之后，用 $O(1)$ 的时间来查询区间的最值 (因为区间最值满足区间加法) 知道了这个再来看这道题： 为什么二分答案就不说了，答案显然满足单调性 怎么建表呢，我们发现，这道题要求的是区间内的最大值减去最小值，所以自然而然的想到了搞出来两个 ST表，一个维护最大值，一个维护最小值。 然后对于每一个二分答案的 $MID$，$O(n)$ 的枚举花盆的左端点放在哪里(因为已经二分出了 $MID$，所以知道了左端点，就可以求出右端点了)，$O(1)$ 的查询最大值减去最小值是否满足题意就好了。 还有一个要注意的是题目里坐标和编号不对应，所以数组要开到坐标那么大。 时间复杂度 $O(nlogn)$ (比楼下 $O(n)$ 的单调队列慢一点) ``` #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #define N 1000005 int n,d; int maxzb; int stmin[N][21]; int stmax[N][21]; int query(int l,int r){ int t=log2(r-l+1); int maxn=std::max(stmax[l][t],stmax[r-(1<<t)+1][t]); int minn=std::min(stmin[l][t],stmin[r-(1<<t)+1][t]); return maxn-minn; } bool check(int x){ for(int i=1;i<=maxzb-x;i++){ int to=i+x; if(query(i,to)>=d) return 1; } return 0; } signed main(){ scanf("%d%d",&n,&d); memset(stmin,0x3f,sizeof stmin); for(int x,y,i=1;i<=n;i++){ scanf("%d%d",&x,&y); maxzb=std::max(maxzb,x); stmax[x][0]=std::max(stmax[x][0],y); stmin[x][0]=std::min(stmin[x][0],y); } int t=log2(maxzb); for(int j=1;j<=t;j++){ for(int i=1;i<=maxzb-(1<<j)+1;i++){ stmax[i][j]=std::max(stmax[i][j-1],stmax[i+(1<<j-1)][j-1]); stmin[i][j]=std::min(stmin[i][j-1],stmin[i+(1<<j-1)][j-1]); } } int l=1,r=maxzb; int ans=-1; while(l<=r){ int mid=l+r>>1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } printf("%d\n",ans); return 0; } ```