bzoj4237 稻草人——分治
2024-09-19 20:13:29
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=4237
分治;
先把所有点按 y 排序,然后二分递归;
对于每个 mid ,计算经过它的矩形的个数,把上面的每个点当做右上角,考虑下面多少点可以作为左下角;
上面的限制只有前面的 y 大于等于自己的 y,所以维护递增的单调栈;
下面的限制是后面的 y 小于等于自己的 y,所以维护递减的单调栈;
还要注意 x 的限制,二分找到栈内满足条件的最前面的点,到栈顶的元素个数就是对答案的贡献。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxn=2e5+;
int n,tpa,tpb,sta[maxn],stb[maxn];
long long ans;
struct N{int x,y;}s[maxn];
bool cmp(N a,N b){return a.y<b.y;}
bool cmpx(N a,N b){return a.x<b.x;}
void cdq(int l,int r)
{
if(l==r)return;
int mid=((l+r)>>);
cdq(l,mid); cdq(mid+,r);
sort(s+l,s+mid+,cmpx); sort(s+mid+,s+r+,cmpx);//请不要写成 s+1
int p=l; tpa=tpb=;
for(int i=mid+;i<=r;i++)
{
while(s[sta[tpa]].y>=s[i].y && tpa)tpa--;
int pos=s[sta[tpa]].x; sta[++tpa]=i;
while(p<=mid && s[p].x<s[i].x)
{
while(s[stb[tpb]].y<=s[p].y && tpb)tpb--;
stb[++tpb]=p; p++;
}
int L=,R=tpb,res=-;
while(L<=R)
{
int Mid=((L+R)>>);
if(s[stb[Mid]].x>pos)res=Mid,R=Mid-;
else L=Mid+;
}
if(res!=-)ans+=tpb-res+;
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d%d",&s[i].x,&s[i].y);
s[].x=s[].y=-;//
sort(s+,s+n+,cmp);
cdq(,n);
printf("%lld\n",ans);
return ;
}
最新文章
- SQL Server 2014新功能PPT
- 细说Linq之Aggregate
- WinForm timer控件
- ubuntu.sh: 113: ubuntu.sh: Syntax error: ";("; unexpected
- .NET连接池的配置 【转】
- BICEP单元测试计划-四则运算-测试
- mobileconfig文件的签名和认证(signed、verified)
- 一种轻量的openresty路由设计
- Win7设置承载网络 分类: 网络 2014-10-30 09:08 105人阅读 评论(0) 收藏
- logcat使用
- #include <;set>;
- Andriod中绘(画)图----Canvas的使用具体解释
- poj 3070 &;&; nyoj 148 矩阵快速幂
- Vue UI:Vue开发者必不可少的工具
- 在写php项目时 修改外部css或js文件没有效果
- 《ABCD组团队》第二次作业
- ef 增加或者更新的习惯思维
- LitJson的用法
- HADOOP HA 踩坑 - org.apache.hadoop.hdfs.qjournal.protocol.JournalNotFormattedException: Journal Storage Directory /mnt/data1/hadoop/dfs/journal/hdfscluster not formatted
- cocos2dx 3.x(for 循环让精灵从中间往上下两边排列)