The Preliminary Contest for ICPC Asia Xuzhou 2019 E XKC's basketball team [单调栈上二分]

也许更好的阅读体验

$Description$Description

给n个数，与一个数m，求 $a_i$ai​右边最后一个至少比 $a_i$ai​大 $m$m的数与这个数之间有多少个数
$2\le n\le 5\ast 10^5,0\le m\le 10^9$2≤n≤5∗105,0≤m≤109

$Solution$Solution

这道题看了下其他题解都是用线段树写的
虽然线段树是一个很显然的方法，但是代码冗长并且常数较大 (可能是我不喜欢数据结构)
如果把数据范围开大 $3,4$3,4倍就妥妥的 $T$T了
这里提供一个单调栈的打法
从后往前考虑每个位置
我们把每个答案为 $-1$−1的位置的数用一个递增的单调栈维护起来
每次到一个位置就二分这个单调栈，找到第一个比它大至少 $m$m的位置，然后答案就是它们的距离减 $1$1
为什么只有 $-1$−1的位置要放到单调栈里面呢
因为有比它大至少 $m$m的位置，所以这个位置永远不会是最优的

$Code$Code

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年09月16日 星期一 20时46分27秒 *******************************/
#include <cstdio>
#include <fstream>
using namespace std;
const int maxn = 1000006;
int n,m,mx=-1,loc,t;
int h[maxn],ans[maxn],q[maxn];
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i)	scanf("%d",&h[i]);
	ans[n]=-1,q[++t]=n;
	for (int i=n-1;i>=1;--i){
		int g=h[i]+m;
		if (h[q[t]]<g){
			ans[i]=-1;
			if (h[q[t]]<h[i])	q[++t]=i;
		}
		else{
			int l=1,r=t;
			while (l<r){
				int mid=(l+r)>>1;
				if (h[q[mid]]>=g)	r=mid;
				else	l=mid+1;
			}
			ans[i]=q[l]-i-1;
		}
	}
	for (int i=1;i<=n-1;++i)	printf("%d ",ans[i]);
	printf("-1\n");
	return 0;
}

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧