做这道题之前，建议先做POJ 1151 Atlantis，经典的扫描线求矩阵的面积并
参考连接：
http://www.cnblogs.com/scau20110726/archive/2013/04/13/3018702.html
线段树辅助——扫描线法计算矩形周长并（轮廓线）:
http://www.cnblogs.com/scau20110726/archive/2013/04/13/3018687.html
http://blog.csdn.net/ophunter/article/details/9129557
题意：求几个矩形并后的周长
思路：这和求矩形并的面积差不多，也是要用到扫描线，一根一根地扫描。只不过这里比求面积的要麻烦点。
离散化就不用说了，具体说下如何求周长吧。
首先将横线的信息存起来，按照y从小到大排序，当y相同时，矩阵的下边界排在前面，上边界排在后面，具体原因后面会有说明。
然后一条一条的开始插入，计算周长分为两种：
1.计算垂直方向的周长时，首先我们要知道整个区间被分成了多少段，即该区间被多少条线段覆盖，设为m，
那么垂直方向的增量即为2*m*(y2-y1)，(y2-y1)即为当前扫描线的纵坐标和前一次纵坐标的差值。
2.计算水平方向的周长时，统计当前区间的总长度，同时记录上一个状态的时候区间总长度，那么这2次区间总长度之差的绝对值
就是插入当前扫描线后，总区间内水平方向的增量。
不过这里有一点要注意的是：会有重边的出现。
当纵坐标一样时，为了防止矩阵A的上边界和矩阵B的下边界重合时，实际上增量为0。
但如果先加入矩阵A的上边界l1，即先删除，当前区间总长度为绿色的线条1，现在变为蓝色的线条2，增量为某值a；
再加入矩阵B的下边界l2，上一次区间总长度为线条2，现在变为紫色的线条3，增量又为a，这样导致多计算了2*a。
所以正确的是应该先扫描矩阵B的下边界(tp=1)，再扫描矩阵A的上边界(tp=-1)，即y相同时，tp=1的排在前面。即先插入，再删除。
这样先插入l2，区间总长度不变，再插入l1，区间总长度仍不变，这样增量就为0.
不过测试的数据里没有出现重边的情况，所以AC的方法并不一定是正确的。
我线段树建立的叶子节点是区间(a,a+1)，而不是点，这样是为了方便求区间长度。
更新的时候，是直接更新到叶子节点的。
本想在更新时，用lazy标记，这样不必更新到叶子节点，但是样例一直不过。
后来调试时候，发现当更新某一个节点时，该节点cnt=1，但是父节点的cnt仍是0。
这样如果某次更新正好更新到父节点时，cnt为0，但实际上父节点中所包含的区间中有部分cnt=1，这样就导致更新的时候会不正确。
因此正确的更新还是要更新到叶子节点。
最后还要说明一下的是：POJ 上面只有一组数据，而HDU 上面有多组数据。
附上代码：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#define lson rt<<1,L,mid
#define rson rt<<1|1,mid,R using namespace std;
const int maxn=;
int n,cnt=; //n为矩形的个数，cnt为离散后的点x的个数
int hashval[maxn]; //x坐标对应的离散的值
int xval[maxn]; //存储所有的x坐标的值
int idx=; //xval存储的数的个数 struct Line {
int l,r,y; //l：左端点 r：右端点 y：纵坐标
int tp; //标记，1为矩形的下边界，-1为矩形的上边界
bool operator<(const Line tmp)const {
/*
当纵坐标一样时，矩阵的下边界(tp=1)排在前面，矩阵的上边界(tp=-1)排在后面
*/
if(y==tmp.y)
return tp>tmp.tp;
return y<tmp.y;
}
} line[maxn];
int lnum=; struct Node {
int lp,rp; //标记左右端点是否被线条覆盖，1为是，0为否，用于在pushUp时，统计父亲的num值
int cnt; //表示这个区间被覆盖的次数
int len; //这个区间被覆盖的长度
int num; //该区间被多少条线段覆盖
} tree[maxn<<]; //二分搜索离散后的值
int binarySearch(int m) {
int l=,r=cnt,mid;
while(r>=l) {
mid=(l+r)>>;
if(hashval[mid]==m)
return mid;
if(hashval[mid]<m)
l=mid+;
else
r=mid-;
}
} void pushUp(int rt) {
tree[rt].lp=tree[rt<<].lp;
tree[rt].rp=tree[rt<<|].rp;
tree[rt].num=tree[rt<<].num+tree[rt<<|].num;
tree[rt].len=tree[rt<<].len+tree[rt<<|].len;
if(tree[rt<<].rp== && tree[rt<<|].lp==)
tree[rt].num--;
}
void build(int rt,int L,int R) {
tree[rt].cnt=tree[rt].lp=tree[rt].rp=tree[rt].num=tree[rt].len=;
if(L+==R)
return;
int mid=(L+R)>>;
build(lson);
build(rson);
} void update(int rt,int L,int R,int l,int r,int p) {
if(l<=L&&R<=r) {
tree[rt].cnt+=p;
if(tree[rt].cnt) {
tree[rt].lp=tree[rt].rp=;
tree[rt].num=;
tree[rt].len=hashval[R]-hashval[L];
} else {
tree[rt].lp=tree[rt].rp=;
tree[rt].num=tree[rt].len=;
}
return;
}
int mid=(L+R)>>;
if(l<mid)
update(lson,l,r,p);
if(r>mid)
update(rson,l,r,p);
pushUp(rt);
} int main() {
int x1,y1,x2,y2;
while(scanf("%d",&n)!=EOF) {
cnt=idx=;
for(int i=; i<=n; i++) {
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
line[*i-].l=x1;line[*i-].r=x2;line[*i-].y=y1;line[*i-].tp=;
line[*i].l=x1;line[*i].r=x2;line[*i].y=y2;line[*i].tp=-;
xval[++idx]=x1;
xval[++idx]=x2;
}
lnum=*n;
sort(line+,line+lnum+);
sort(xval+,xval+idx+);
//对x坐标进行离散
hashval[++cnt]=xval[];
for(int i=; i<=idx; i++) {
if(xval[i]!=xval[i-]) {
hashval[++cnt]=xval[i];
}
}
build(,,cnt);
long long ans=;
int last=; //last记录插入上一次扫描线的区间总长度
int x,y;
for(int i=; i<=lnum; i++) {
ans+=tree[].num**(line[i].y-line[i-].y);
x=line[i].l;
y=line[i].r;
x=binarySearch(x);
y=binarySearch(y);
for(int j=x; j<=y-; j++)
update(,,cnt,j,j+,line[i].tp);
ans+=abs(tree[].len-last);
last=tree[].len;
}
printf("%I64d\n",ans);
}
return ;
}
后来写了个区间更新的，代码贴上：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define lson rt<<1,L,mid
#define rson rt<<1|1,mid+1,R
/*
区间更新AC 15ms
把之前写的单点更新的提交了下，0ms。。。
区间更新反而比单点更新慢。。。郁闷。。。 这次建立的叶子节点是(a,a)，所以在二分查找对应的区间(a,b)时，右端点b要减1
*/
using namespace std;
const int maxn=+;
int n,cnt; int hashx[maxn<<];
struct Node{
int cnt;
int lp,rp;
int num;
int len;
}tree[maxn<<]; struct Line{
int l,r,y;
int tp;
bool operator<(const Line tmp)const{
if(y==tmp.y){
return tp>tmp.tp;
}
else
return y<tmp.y;
}
}line[maxn<<]; void build(int rt,int L,int R){
tree[rt].cnt=tree[rt].lp=tree[rt].rp=tree[rt].num=;
tree[rt].len=;
if(L==R)
return;
int mid=(L+R)>>;
build(lson);
build(rson);
} void pushUp(int rt,int L,int R){
if(tree[rt].cnt){
tree[rt].len=hashx[R+]-hashx[L];
tree[rt].lp=tree[rt].rp=;
tree[rt].num=;
}
else{
if(L==R){
tree[rt].len=;
tree[rt].lp=tree[rt].rp=tree[rt].num=;
}
else{
//父节点cnt=0，但可能子节点有cnt不为0的，所以父亲要从子节点处获得更新
tree[rt].lp=tree[rt<<].lp;
tree[rt].rp=tree[rt<<|].rp;
tree[rt].len=tree[rt<<].len+tree[rt<<|].len;
tree[rt].num=tree[rt<<].num+tree[rt<<|].num;
if(tree[rt<<].rp && tree[rt<<|].lp)
tree[rt].num--; //减去一个重复计算的
}
}
} void update(int rt,int L,int R,int l,int r,int val){
if(l<=L&&R<=r){
tree[rt].cnt+=val;
pushUp(rt,L,R); //区间更新这里不能忘
return;
}
int mid=(L+R)>>;
if(l<=mid)
update(lson,l,r,val);
if(r>mid)
update(rson,l,r,val);
pushUp(rt,L,R);
} int binarySearch(int x,int n){
int l=,r=n+,mid;
while(r-l>){
mid=(l+r)>>;
if(hashx[mid]<=x)
l=mid;
else
r=mid;
}
return l;
} int main()
{
int x1,x2,y1,y2;
while(scanf("%d",&n)!=EOF){
cnt=;
for(int i=;i<=n;i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
line[*i-].y=y1;line[*i-].l=x1;line[*i-].r=x2;line[*i-].tp=;
line[*i].y=y2;line[*i].l=x1;line[*i].r=x2;line[*i].tp=-;
hashx[cnt++]=x1;
hashx[cnt++]=x2;
}
n=n*;
sort(hashx+,hashx+cnt);
sort(line+,line+n+);
int idx=;
for(int i=;i<=n;i++){
if(hashx[i]!=hashx[i-])
hashx[++idx]=hashx[i];
}
build(,,idx);
long long ans=;
int last=;
for(int i=;i<=n;i++){
ans+=(line[i].y-line[i-].y)**tree[].num;
int a=binarySearch(line[i].l,idx);
int b=binarySearch(line[i].r,idx)-;
update(,,idx,a,b,line[i].tp);
ans+=abs(tree[].len-last);
last=tree[].len;
}
printf("%I64d\n",ans);
}
return ;
}