一、矩阵面积并 （HDU 1542）

#include<bits/stdc++.h>
#define N 2010
using namespace std;

struct seg
{
    int l,r,h,d;
    seg(){}
    seg(int l,int r,int h,int d):l(l),r(r),h(h),d(d){}
    bool operator < (const seg a)const{return h<a.h;}
}a[N];

int i,j,k,l,n,m,t,h;
int c[N<<1],sum[N<<2],cnt[N<<2];

void push_up(int x,int l,int r)
{
    if (cnt[x])sum[x]=c[r+1]-c[l];else
    if (l==r)sum[x]=0;else
    sum[x]=sum[x<<1]+sum[x<<1|1];
}

void updata(int x,int l,int r,int fl,int fr,int v)
{
    if (fl<=l && r<=fr)
    {
        cnt[x]+=v;
        push_up(x,l,r);
        return;
    }
    int t=(l+r)>>1;
    if (fl<=t)updata(x<<1,l,t,fl,fr,v);
    if (fr>t)updata(x<<1|1,t+1,r,fl,fr,v);
    push_up(x,l,r);
}

int main()
{
    int x,y,xx,yy;
    while (~scanf("%d",&n) && n)
    {
        for (i=1;i<=n;i++)
        {
            scanf("%d%d%d%d",&x,&y,&xx,&yy);
            a[i]=seg(x,xx,y,1);
            a[i+n]=seg(x,xx,yy,-1);
            c[i]=x;c[i+n]=xx;
        }
        n<<=1;
        sort(a+1,a+1+n);
        sort(c+1,c+1+n);
        m=unique(c+1,c+n+1)-c-1;
        int ans=0;
        memset(sum,0,sizeof sum);
        memset(cnt,0,sizeof cnt);
        for (i=1;i<n;i++)
        {
            int fl=lower_bound(c+1,c+m+1,a[i].l)-c,fr=lower_bound(c+1,c+m+1,a[i].r)-c;
            if (fl<fr)updata(1,1,m,fl,fr-1,a[i].d);
            ans+=sum[1]*(a[i+1].h-a[i].h);
        }
        printf("%d\n",ans);
    }
    puts("*");
}

二、矩阵周长并（HDU 1828）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 5010
#define MAX 10100
#define lch(i) ((i)<<1)
#define rch(i) ((i)<<1|1)

struct segment
{
    int l,r,h,v;
}s[2*N];

struct node
{
    int l,r,lp,rp,cnt,len,num;
    int mid()
    { return (l+r)>>1; }
}t[2*MAX*4];

int cmp(struct segment p ,struct segment q)
{
    return p.h<q.h;
}

void build(int l ,int r, int rt)
{
    t[rt].l=l; t[rt].r=r;
    t[rt].cnt=t[rt].len=0;
    t[rt].lp=t[rt].rp=t[rt].num=0;
    if(l==r) return ;
    int mid=t[rt].mid();
    build(l,mid,lch(rt));
    build(mid+1,r,rch(rt));
}

void cal(int rt)
{
    if(t[rt].cnt)
    {
        t[rt].len=t[rt].r-t[rt].l+1;
        t[rt].lp=t[rt].rp=1;
        t[rt].num=1;
    }
    else if(t[rt].l == t[rt].r) //叶子
    {
        t[rt].len=0;
        t[rt].lp=t[rt].rp=0;
        t[rt].num=0;
    }
    else
    {
        t[rt].len=t[lch(rt)].len+t[rch(rt)].len;
        t[rt].lp=t[lch(rt)].lp; 
        t[rt].rp=t[rch(rt)].rp;
        t[rt].num=t[lch(rt)].num + t[rch(rt)].num - (t[lch(rt)].rp&t[rch(rt)].lp);
    }
}

void updata(int l ,int r ,int v ,int rt)
{
    if(t[rt].l==l && t[rt].r==r) //目标区间
    {
        t[rt].cnt += v;
        cal(rt);
        return ;
    }
    int mid=t[rt].mid();
    if(r<=mid)     updata(l,r,v,lch(rt));
    else if(l>mid) updata(l,r,v,rch(rt));
    else
    {
        updata(l,mid,v,lch(rt));
        updata(mid+1,r,v,rch(rt));
    }
    cal(rt);
}

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) 
        { puts("0"); continue; }
        int i,maxx,minx,m;
        for(i=0,m=0,maxx=-MAX,minx=MAX; i<n; i++,m+=2)
        {
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            maxx=max(maxx,x2);
            minx=min(minx,x1);
            s[m].l=x1;   s[m].r=x2;   s[m].h=y1;   s[m].v=1;
            s[m+1].l=x1; s[m+1].r=x2; s[m+1].h=y2; s[m+1].v=-1;
        }
        sort(s,s+m,cmp);
        build(minx,maxx-1,1);
        int res=0 , prelen=0;
        s[m]=s[m-1]; //每次处理循环的最后一次
        for(int i=0; i<m; i++)
        {
            updata(s[i].l,s[i].r-1,s[i].v,1);
            res += abs(t[1].len-prelen); //计算横线部分
            res += (s[i+1].h-s[i].h)*(2*t[1].num); //计算竖线部分
            prelen=t[1].len;
        }
        printf("%d\n",res);
    }
    return 0;
}