从昨晚上开始看,终于搞明白线段树怎么求面积并了.忘得快,得记.

对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();
        }
    }
}