首页 > 代码库 > Picture
Picture
线段树+扫描线
对于每条线段,分横竖考虑,排序,坐标第一关键字,左右第2关键字
对于矩形左边线段,先统计这条线段区域0的个数,在把线段树中这条线段覆盖的区域+1,右边反过来
一定要记得右端点-1(因为题目给的是点,实际上是区间)
例如1,3。其实只覆盖2个区间(1,2;2,3)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using
namespace
std;
struct
data1{
int
l,r,k,p;
}x[10001],y[10001];
struct
data2{
int
x,s,l,r,la;
}tree[80001];
int
n;
bool
cmp(data1 a,data1 b)
{
if
(a.k==b.k)
return
a.p>b.p;
return
a.k<b.k;
}
void
down(
int
x)
{
tree[x*2].x+=tree[x].la;
tree[x*2].la+=tree[x].la;
tree[x*2+1].x+=tree[x].la;
tree[x*2+1].la+=tree[x].la;
tree[x].la=0;
}
void
up(
int
x)
{
tree[x].x=min(tree[x*2].x,tree[x*2+1].x);
if
(tree[x*2].x==tree[x*2+1].x)tree[x].s=tree[x*2].s+tree[x*2+1].s;
if
(tree[x*2].x<tree[x*2+1].x)tree[x].s=tree[x*2].s;
if
(tree[x*2].x>tree[x*2+1].x)tree[x].s=tree[x*2+1].s;
}
void
init(
int
x,
int
l,
int
r)
{
tree[x].l=l;tree[x].r=r;tree[x].la=0;tree[x].x=0;
if
(l==r){tree[x].s=1;
return
;}
init(x*2,l,(l+r)/2);init(x*2+1,(l+r)/2+1,r);
up(x);
}
void
add(
int
x,
int
l,
int
r,
int
k)
{
if
(tree[x].l==l&&tree[x].r==r){tree[x].x+=k;tree[x].la+=k;
return
;}
down(x);
int
mid=(tree[x].l+tree[x].r)/2;
if
(r<=mid)add(x*2,l,r,k);
else
if
(l>mid)add(x*2+1,l,r,k);
else
{add(x*2,l,mid,k);add(x*2+1,mid+1,r,k);}
up(x);
}
void
query(
int
x,
int
l,
int
r,
int
&ansx,
int
&anss)
{
if
(tree[x].l==l&&tree[x].r==r)
{
if
(ansx==tree[x].x)anss+=tree[x].s;
if
(tree[x].x<ansx)anss=tree[x].s;
ansx=min(ansx,tree[x].x);
return
;
}
down(x);
int
mid=(tree[x].l+tree[x].r)/2;
if
(r<=mid)query(x*2,l,r,ansx,anss);
else
if
(l>mid)query(x*2+1,l,r,ansx,anss);
else
{query(x*2,l,mid,ansx,anss);query(x*2+1,mid+1,r,ansx,anss);}
}
int
main()
{
scanf
(
"%d"
,&n);
for
(
int
i=1;i<=n;i++)
{
int
_x1,_y1,_x2,_y2;
scanf
(
"%d%d%d%d"
,&_x1,&_y1,&_x2,&_y2);
_x1+=10000;_x2+=10000;_y1+=10000;_y2+=10000;
y[i*2-1].l=_x1;y[i*2-1].r=_x2-1;y[i*2-1].k=_y1;y[i*2-1].p=1;
y[i*2].l=_x1;y[i*2].r=_x2-1;y[i*2].k=_y2;y[i*2].p=-1;
x[i*2-1].l=_y1;x[i*2-1].r=_y2-1;x[i*2-1].k=_x1;x[i*2-1].p=1;
x[i*2].l=_y1;x[i*2].r=_y2-1;x[i*2].k=_x2;x[i*2].p=-1;
}
n*=2;
int
ans=0;
sort(x+1,x+n+1,cmp);sort(y+1,y+n+1,cmp);
init(1,0,20000);
for
(
int
i=1;i<=n;i++)
{
if
(x[i].p==-1)add(1,x[i].l,x[i].r,-1);
int
anss=0,ansx=999999999;query(1,x[i].l,x[i].r,ansx,anss);
if
(x[i].p==1)add(1,x[i].l,x[i].r,1);
if
(ansx==0)ans+=anss;
}
init(1,0,20000);
for
(
int
i=1;i<=n;i++)
{
if
(y[i].p==-1)add(1,y[i].l,y[i].r,-1);
int
anss=0,ansx=999999999;query(1,y[i].l,y[i].r,ansx,anss);
if
(y[i].p==1)add(1,y[i].l,y[i].r,1);
if
(ansx==0)ans+=anss;
}
cout<<ans;
return
0;
}
Picture
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。