BZOJ 1818 线段树+扫描线
2024-08-31 11:18:12
思路:
可以把题目转化成
给你一些沿坐标轴方向的线段 让你求交点个数
然后就线段树+扫描线 搞一搞
(线段不包含断点 最后+n 这种方式 比线段包含断点+各种特判要好写得多)
//By SiriusRen
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100005;
int n,stkx[N],stky[N],topx,topy,top,tree[N*4];long long ans;
struct Node{int x,y;}node[N];
bool cmp1(Node a,Node b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;}
bool cmp2(Node a,Node b){if(a.y!=b.y)return a.y<b.y;return a.x<b.x;}
struct Movement{
int time,num,move,l,r;
Movement(int x,int y,int z){time=x,num=y,move=z;}
Movement(int x,int y,int z,int flg){time=x,l=y,r=z,move=flg;}
Movement(){}
friend bool operator<(Movement a,Movement b){
if(a.time!=b.time)return a.time<b.time;
return a.move<b.move;
}
}movement[N*3];
void insert(int l,int r,int pos,int num,int wei){
if(l==r){tree[pos]+=wei;return;}
int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;
if(mid<num)insert(mid+1,r,rson,num,wei);
else insert(l,mid,lson,num,wei);
tree[pos]=tree[lson]+tree[rson];
}
int query(int l,int r,int pos,int L,int R){
if(L>R)return 0;
if(l>=L&&r<=R){return tree[pos];}
int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;
if(mid<L)return query(mid+1,r,rson,L,R);
else if(mid>=R)return query(l,mid,lson,L,R);
else return query(l,mid,lson,L,R)+query(mid+1,r,rson,L,R);
}
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&node[i].x,&node[i].y),
stkx[++topx]=node[i].x,stky[++topy]=node[i].y;
sort(stkx+1,stkx+1+topx),sort(stky+1,stky+1+topy);
topx=unique(stkx+1,stkx+1+topx)-stkx-1;
topy=unique(stky+1,stky+1+topy)-stky-1;
for(int i=1;i<=n;i++)
node[i].x=lower_bound(stkx+1,stkx+1+topx,node[i].x)-stkx,
node[i].y=lower_bound(stky+1,stky+1+topy,node[i].y)-stky;
sort(node+1,node+1+n,cmp1);
for(int i=1;i<=n;i++)if(node[i].x==node[i-1].x)
movement[++top]=Movement(node[i-1].y,node[i].x,1),
movement[++top]=Movement(node[i].y,node[i].x,-1);
sort(node+1,node+1+n,cmp2);
for(int i=1;i<=n;i++)if(node[i].y==node[i-1].y)
movement[++top]=Movement(node[i].y,node[i-1].x,node[i].x,0);
sort(movement+1,movement+1+top);
for(int i=1;i<=top;i++)
if(movement[i].move)insert(1,topx,1,movement[i].num,movement[i].move);
else ans+=query(1,topx,1,movement[i].l+1,movement[i].r-1);
printf("%lld\n",ans+n);
}
最新文章
- NOSDK--SDK一键打包及统一接入的实现(前言)
- 链表原地反转Demo
- log4cplus 直接创建logger 对象
- 基于SSL协议的双向认证 - 双向认证 [3]
- 有助于提高你的 Web 开发技能的7个模式库
- Windows 下安装项目管理工具 Redmine 1.1.2
- nslayoutConstraint
- &;&;和||的那点事儿
- IOS的一些尺寸
- PHP 性能分析第二篇: Xhgui In-Depth
- org.hibernate.PersistentObjectException: detached entity passed to persist异常
- [ES6] 23. Rest Parameters &; Spread Parameters
- 数据结构算法及应用&mdash;&mdash;二叉树
- asp.net 一个简单的登录控制
- FPGA 设计流程,延迟,时间
- linuxlab下虚拟板与主机通信
- git使用步骤
- 关于在html中直接引入less文件遇到的小问题
- 如果你在it院校学习累了,你能干什么?
- 【HDU 5363】Key Set(和为偶数的子集个数)