BZOJ3356 : [Usaco2004 Jan]禁闭围栏
2024-09-19 21:14:47
首先将坐标离散化,考虑从左往右扫描线
碰到插入操作则插入
碰到删除操作的:
当前包含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;
}
最新文章
- 【小错误】Device eth2 has different MAC address than expected, ignoring.
- sqlalchemy 优化count()……
- IOS酷炫的下拉刷新链接收集
- PHP中的替代语法(冒号、endif、endwhile、endfor)
- .Net Core下如何管理配置文件(转载)
- JSP导出Excel文件
- Java基础学习(三)&mdash;面向对象(上)
- Android图表库MPAndroidChart(十三)——简约的底部柱状图
- Android Studio 使用SlidingMenu侧滑菜单
- Unity历史
- Python 实现获取微信好友信息
- Elasticsearch必备技能之索引迁移
- js实现简易版validate
- Educational Codeforces Round 61 (Rated for Div. 2)
- html5 area实例
- 如何用AJax提交name[]数组?
- JavaScript Dom 绑定事件
- BZOJ2669 [cqoi2012]局部极小值 状压DP 容斥原理
- git checkout -b 分支name 分支的新建, 切换, 删除, 查看
- LoadRunner 压测场景制定以及报告分析