【BZOJ4237】稻草人（CDQ分治，单调栈）

时间：2023-12-16 22:42:38

【BZOJ4237】稻草人（CDQ分治，单调栈）

题面

BZOJ

题解

\(CDQ\)分治好题呀

假设固定一个左下角的点

那么，我们可以找到的右下角长什么样子？？？

【BZOJ4237】稻草人（CDQ分治，单调栈）

发现什么？

在右侧是一个单调递减的东西

那么，对于每一个已经固定好的左下角

我们可以通过单调栈来维护答案

既然只有左下角对右上角会产生贡献

那么，按照\(x\)轴排序之后可以\(CDQ\)分治

\(CDQ\)分治怎么搞？

如果在上面的基础上多了几个点。。

【BZOJ4237】稻草人（CDQ分治，单调栈）

那几根棕色的线链接的连是不能贡献答案的

我们来看看：

这些点的\(y\)轴都在当前这个左下角的右上方那个左下角的上面

（这句话好晕呀。。。）

但是在那么点下面的右上角却是可行的

再来一个点试试。。

【BZOJ4237】稻草人（CDQ分治，单调栈）

这个有点乱。。。

我们发现\(B\)点受到了\(A\)的限制

但是\(C\)点却没有任何限制

我们发现了什么关系？

\(B_x<A_x<C_x\)

也就是说和\(x\)坐标有关系

那么，其实这题已经很显然了

对于\(CDQ\)分治的左右两侧考虑贡献

首先按照\(y\)轴从上往下依次加点

右侧的用单调栈维护，使得\(x\)轴递增

而左侧要反过来，使得\(x\)轴递减

这样的话，每个左侧的点产生的贡献就会被单调栈中的前一个元素所影响

那么用前一个元素在右边的单调栈中二分一下就可以啦

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 222222

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int n;

struct Node{int x,y;}p[MAX];

bool operator<(Node a,Node b){return a.x<b.x;}

bool cmp(Node a,Node b){return a.y>b.y;}

ll ans;

int S[MAX],top;

int Q[MAX],H,T;

void CDQ(int l,int r)

{

	if(l==r)return;

	int mid=(l+r)>>1;

	CDQ(l,mid);CDQ(mid+1,r);

	sort(&p[l],&p[mid+1],cmp);

	sort(&p[mid+1],&p[r+1],cmp);

	int h=mid+1;top=0;T=0;

	for(int i=l;i<=mid;++i)

	{

		while(h<=r&&p[h].y>p[i].y)

		{

			while(top&&p[S[top]].x>p[h].x)--top;

			S[++top]=h++;

		}

		while(T&&p[Q[T]].x<p[i].x)--T;

		Q[++T]=i;

		if(T==1)

			ans+=top;

		else

		{

			int L=1,R=top,pls=top+1;

			while(L<=R)

			{

				int mid=(L+R)>>1;

				if(p[S[mid]].y>p[Q[T-1]].y)L=mid+1;

				else pls=mid,R=mid-1;

			}

			ans+=top-pls+1;

		}

	}

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)p[i].x=read(),p[i].y=read();

	sort(&p[1],&p[n+1]);

	CDQ(1,n);

	printf("%lld\n",ans);

	return 0;

}

相关文章