从昨晚上开始看,终于搞明白线段树怎么求面积并了.忘得快,得记.
对y轴上的坐标做离散化,在y轴上建立线段树.
对每一个矩阵的左右边,建立入边和出边,并记录在y轴上的投影.把所有的入边和出边排序,从左到右按x轴方向扫描,若扫到的是入边,则在线段树上对投影线段的val加1,若出边则减一.
边扫描,边统计和上一条边之间的扫过的面积,即x轴上的跨度乘y轴上测度(测度为在线段树上val>1的线段的总长度,不必连续).测度可以用线段树查询,也可以对线段增加一个属性,并在插入过程中动态的计算,对查询量多的情况如poj3695更快.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef __int64 i64;
#define IN false
#define OUT true
i64 q[40001],top;
struct edge
{
i64 x,y1,y2;
bool type;
void init(i64 a,i64 h,bool t)
{ x=a,y1=0;y2=h;type=t; }
} e[80000]; int tot;
bool cmp(const edge& e1,const edge& e2)
{
return e1.x<e2.x;
}
struct node { int l,r,val; } tree[80000*3];
void create(int l,int r,int root)
{
tree[root].l=l;tree[root].r=r;
tree[root].val=0;
if(l<r-1)
{
int m=(l+r)/2;
create(l,m,root*2);
create(m,r,root*2+1);
}
}
void update(int l,int r,int root,int val)
{
if(l==tree[root].l && tree[root].r==r)
tree[root].val+=val;
else if(tree[root].l<tree[root].r-1)
{
int m=(tree[root].l+tree[root].r)/2;
if(r<=m) update(l,r,root*2,val);
else if(l>=m) update(l,r,root*2+1,val);
else
{
update(l,m,root*2,val);
update(m,r,root*2+1,val);
}
}
}
i64 query(int root)
{
if(tree[root].val>0)
return q[tree[root].r]-q[tree[root].l];
else if(tree[root].l<tree[root].r-1)
return query(root*2) + query(root*2+1);
return 0;
}
int rank(i64 y)//二分离散化后的位置
{
int l=0,r=top-1,m;
while(l<=r)
{
m=(l+r)>>1;
if(q[m]==y) return m;
else if(q[m]>y) r=m-1;
else l=m+1;
}
}
i64 a[40000],b[40000],h[40000];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
int i,j,n;
i64 ans;
scanf("%d",&n);
q[0]=0;top=1;
for(i=0,tot=0;i<n;i++)
{
scanf("%I64d%I64d%I64d",a+i,b+i,h+i);
q[top++]=h[i];
}
//离散化
sort(q,q+top);
for(i=1,j=1;i<top;i++)
if(q[i]!=q[i-1])//去重复
q[j++]=q[i];
top=j;
for(i=0;i<n;i++)
{
h[i]=rank(h[i]);//离散化后的值
e[tot++].init(a[i],h[i],IN);//入边
e[tot++].init(b[i],h[i],OUT);//出边
}
create(0,top-1,1);
sort(e,e+2*n,cmp);//对所有入边出边排序
for(ans=0,i=0;i<2*n;i++)//扫描
{
if(i)
ans+=(e[i].x-e[i-1].x)*query(1);
if(e[i].type==IN)
update(e[i].y1,e[i].y2,1,1);
else
update(e[i].y1,e[i].y2,1,-1);
}
printf("%I64d\n",ans);
}
面积并也可以用容斥原理求,不过比线段树慢,这个是poj 3695的TLE的代码:
#include <cstdio>
struct rec
{
int x1,y1,x2,y2,area;
void cross(const rec &r)
{
if(r.x1>x1) x1=r.x1; if(r.y1>y1) y1=r.y1;
if(r.x2<x2) x2=r.x2; if(r.y2<y2) y2=r.y2;
if(x2<x1) x2=x1; if(y2<y1) y2=y1;
area=(x2-x1)*(y2-y1);
}
} r[22];
int cnt,q[22];
int cntone(int k)
{
int ans=0;
while(k)
{
if(k&1) ++ans;
k>>=1;
}
return ans;
}
void solve()
{
int i,j;rec tmp;
int ans=0;
for(i=1;i<(1<<cnt);i++)
{
tmp.y1=tmp.x1=-10000;tmp.y2=tmp.x2=10000;
for(j=1;j<=cnt;j++)
{
if(i&(1<<(j-1)))
tmp.cross(r[q[j]]);
if(tmp.area==0) break;
}
if(cntone(i)&1)
ans+=tmp.area;
else
ans-=tmp.area;
}
printf("%d\n",ans);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
int i,j,n,m,cas=1;
while(scanf("%d%d",&n,&m),(n+m))
{
printf("Case %d:\n",cas++);
for(i=1;i<=n;i++)
scanf("%d%d%d%d",&r[i].x1,&r[i].y1,&r[i].x2,&r[i].y2);
for(i=1;i<=m;i++)
{
printf("Query %d: ",i);
scanf("%d",&cnt);
for(j=1;j<=cnt;j++) scanf("%d",q+j);
solve();
}
}
}
