首先将坐标离散化,考虑从左往右扫描线

碰到插入操作则插入

碰到删除操作的:

当前包含i的矩形数=y1在[1,y2[i]]之间的矩形数-y2在[1,y1[i]-1]之间的矩形数

用两棵树状数组维护即可,时间复杂度$O(n\log n)$。

#include<cstdio>
#include<algorithm>
#define N 500010
int n,m,i,x1,y1,x2,y2,b[N],bl[N],br[N],now,ans=-1,cnt;
struct P{int x,l,r,t;}a[N];
inline bool cmp(P a,P b){return a.x<b.x;}
inline void addl(int x,int y){for(;x<=m;x+=x&-x)bl[x]+=y;}
inline void addr(int x,int y){for(;x<=m;x+=x&-x)br[x]+=y;}
inline int askl(int x){int t=0;for(;x;x-=x&-x)t+=bl[x];return t;}
inline int askr(int x){int t=0;for(;x;x-=x&-x)t+=br[x];return t;}
inline int lower(int x){
int l=1,r=m,mid,t;
while(l<=r)if(b[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1;
return t;
}
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
int main(){
read(n);
while(n--){
read(x1),read(y1),read(x2),read(y2);
a[++m].x=x1,a[m].l=b[m]=y1,a[m].r=y2,a[m].t=1;
a[++m].x=x2,a[m].l=y1,a[m].r=b[m]=y2;
}
for(std::sort(b+1,b+m+1),std::sort(a+1,a+m+1,cmp),i=1;i<=m;i++){
a[i].l=lower(a[i].l),a[i].r=lower(a[i].r);
if(a[i].t)addl(a[i].l,1),addr(a[i].r,1);else{
now=askl(a[i].r)-askr(a[i].l-1);
if(now>ans)ans=now,cnt=1;else if(now==ans)cnt++;
addl(a[i].l,-1),addr(a[i].r,-1);
}
}
return printf("%d %d",ans,cnt),0;
}

  

最新文章

  1. 【小错误】Device eth2 has different MAC address than expected, ignoring.
  2. sqlalchemy 优化count()……
  3. IOS酷炫的下拉刷新链接收集
  4. PHP中的替代语法(冒号、endif、endwhile、endfor)
  5. .Net Core下如何管理配置文件(转载)
  6. JSP导出Excel文件
  7. Java基础学习(三)&mdash;面向对象(上)
  8. Android图表库MPAndroidChart(十三)——简约的底部柱状图
  9. Android Studio 使用SlidingMenu侧滑菜单
  10. Unity历史
  11. Python 实现获取微信好友信息
  12. Elasticsearch必备技能之索引迁移
  13. js实现简易版validate
  14. Educational Codeforces Round 61 (Rated for Div. 2)
  15. html5 area实例
  16. 如何用AJax提交name[]数组?
  17. JavaScript Dom 绑定事件
  18. BZOJ2669 [cqoi2012]局部极小值 状压DP 容斥原理
  19. git checkout -b 分支name 分支的新建, 切换, 删除, 查看
  20. LoadRunner 压测场景制定以及报告分析

热门文章

  1. [POJ1050]To the Max
  2. Coursera台大机器学习课程笔记10 -- Linear Models for Classification
  3. ListBox1控件
  4. 【转】maven命令背后是如何工作的
  5. iOS8 UILocalNotification 和 UIRemoteNotification 使用注意 草稿,正在整理中。。。。
  6. iOS NSURLConnection和异步网络请求
  7. plsql查询数据显示为乱码解决方法
  8. HttpHandler动态生成图片
  9. php 面向对象之封装
  10. 罗辑思维CEO李天田:我们是这样玩儿公司的