ABC372D ABC379F 题解 单调栈二分

一直觉得AT上面学到的东西比CF要多一些，无意捧一踩一，但可能是我太菜的原因，毕竟ABC的题目普遍要比Div.2 简单一些。

好多次碰到这个单调栈里面二分的 trick 了，所以写一篇来总结一下。

ABC 372 D

形象地给定一系列 Buildings 的高度 \(h\) ，保证每个 \(h\) 不相等。

问一共有多少对 \((i,j)\) 满足 \(i< j\) 并且其间不存在比 \(j\) 高的建筑。

我们考虑对于一个 \(j\) ，如果它之前存在一个比它高的建筑 \(j'\) ，那么对于所有 \(j'\) 之前的 \(i\) ，其都不能和 \(j\) 构成一个合法的对，那么这个 \(j\) 对于所有这样的 \(i\) 都是可以不用考虑的。

维护

那么这样的话我们其实就可以倒序枚举 \(i\) ，然后维护一个从顶到底单调递增的单调栈，被弹出的元素一定对现在以及之后所有的 \(i\) 不会有贡献了，所以可以直接弹出。

统计答案

每个答案实际上就是当前栈里的元素个数。

后话

貌似这个版本是不用再单调栈上面二分的，然而我当时如同一个 2b ，不仅使用了二分，甚至还用了差分和前缀和来统计每一个固定的 \(j\) 对 \(i\) 的贡献，而不是直接计算 \(i\) 的答案。

不过这也倒是间接为我在这个强化版问题上面提供了思路，导致想起来没有什么困难。

ABC 379 F

这个就是给定若干个 \((l_i,r_i)\) ，问在 \(r_i\) 的右边有多少建筑能够被 \(l_i\) 和 \(r_i\) 处的建筑同时看到。

分析

不难发现，满足答案的建筑所必须满足的必要条件是能够被 \(l_i\) 看到，当其序号满足在 \(r_i\) 右边的时候，这就变成了一个充要条件了。

所以我们直接离线，然后按左端点从小到大排序，然后倒序枚举区间，把所有 \(l_i\) 之后序号的放进单调栈里面，之后再二分找所有序号大于 \(r_i\) 的即可

维护

不难发现，我们即使不弹出，单调栈里面元素对应的序号也一定是单调的，所以单调栈里可以直接存序号，我们在维护的时候通过序号访问高度，在查询的时候直接查询序号即可。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void re(T &x)
{
	x=0;int f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	x*=f;
} 
template<typename T>inline void wr(T x)
{
	if(x>9)wr(x/10);
	putchar(x%10^48); 
}
inline void out(int x){wr(x),putchar('\n');}
const int N=2e5+10;
int stk[N],top;
struct seg
{
	int l,r,idx;
}a[N];
inline bool cmp(seg x,seg y)
{
	return x.l<y.l;
}
int ans[N]; 
int main()
{
	int n,q;
	cin>>n>>q;
	vector<int> h(n+1);
	for(int i=1;i<=n;++i)re(h[i]);
	for(int i=1;i<=q;++i)
		re(a[i].l),re(a[i].r),a[i].idx=i;
	sort(a+1,a+q+1,cmp);
	auto insert=[&](int x)
	{
		while(top&&h[x]>h[stk[top]])top--;
		stk[++top]=x;
	};
	auto bs=[&](int id)
	{
		if(id>=stk[1])return 0;
		int l=1,r=top;
		while(l<r)
		{
			int mid=(l+r+1)>>1;
			if(stk[mid]>id)l=mid;
			else r=mid-1;
		}
		return l;
	};
	int las=n;
	for(int i=q;i>=1;--i)
	{
		for(int id=las;id>a[i].l;--id)
			insert(id);
		las=a[i].l;	
		ans[a[i].idx]=bs(a[i].r);
//		printf("%d:%d\n",a[i].idx,bs(a[i].r));
	}
	for(int i=1;i<=q;++i)out(ans[i]);
	return 0;
}