题目: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 ;
}

最新文章

  1. SQL Server 2014新功能PPT
  2. 细说Linq之Aggregate
  3. WinForm timer控件
  4. ubuntu.sh: 113: ubuntu.sh: Syntax error: &quot;(&quot; unexpected
  5. .NET连接池的配置 【转】
  6. BICEP单元测试计划-四则运算-测试
  7. mobileconfig文件的签名和认证(signed、verified)
  8. 一种轻量的openresty路由设计
  9. Win7设置承载网络 分类: 网络 2014-10-30 09:08 105人阅读 评论(0) 收藏
  10. logcat使用
  11. #include &lt;set&gt;
  12. Andriod中绘(画)图----Canvas的使用具体解释
  13. poj 3070 &amp;&amp; nyoj 148 矩阵快速幂
  14. Vue UI:Vue开发者必不可少的工具
  15. 在写php项目时 修改外部css或js文件没有效果
  16. 《ABCD组团队》第二次作业
  17. ef 增加或者更新的习惯思维
  18. LitJson的用法
  19. HADOOP HA 踩坑 - org.apache.hadoop.hdfs.qjournal.protocol.JournalNotFormattedException: Journal Storage Directory /mnt/data1/hadoop/dfs/journal/hdfscluster not formatted
  20. cocos2dx 3.x(for 循环让精灵从中间往上下两边排列)

热门文章

  1. vue中的表单验证
  2. 81-Gator Oscillator,加多摆动指标.(2015.7.1)
  3. HUAS Summer Contest#4 D题 DP
  4. prometheus监控mysql
  5. Qt笔记——各种组件和其他细碎用法
  6. 解决idea创建ssm项目找不到mybatis的mapper的xml文件问题
  7. Leetcode 166.分数到小数
  8. 九度oj 题目1190:大整数排序
  9. 看板娘 &amp; 二次元 &amp; live2d
  10. c/c++ 位域的概念