题意： 就是求重叠的矩阵轮廓的周长。
总结：理解线段树最好的方法就是利用样例，或者自己利用模型模拟一遍，然后就是边模拟边想代码的实现。
我的写法是比较正规的二叉树的形式，各个节点描述信息如下。
这个程序经典在于涵盖了线段树的基本操作和节点记录的数据，至于求矩阵面积交，只是缺少了扫描线区间个数的记录，这也是求矩阵周长并的关键。
具体cpp代码如下：
//poj1177Pucture线段树
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
using namespace std;
const int root = 0;
struct Node{
int l,r;
int cover,len,lines;//vover记录覆盖次数，len长度，lines记录并区间数
int lf,rf;//记录左右节点是否被覆盖
int lnd,rnd;//记录左右节点
}node[20005];
int cnt,cnty;
int indexy[10010];//离散纵坐标y的数组
struct Cord{
int x,y1,y2;
bool f;
}cord[10005];//竖线
int n;
void Creat(int p,int l,int r)
{
node[p].l = l; node[p].r = r;
node[p].lf = node[p].rf = 0;
node[p].len = node[p].lines = 0;
if (r - l > 1)
{
int mid = (r+l) >> 1;
node[p].lnd = ++cnt;
Creat(cnt,l,mid); //递归创建左子树
node[p].rnd = ++cnt;
Creat(cnt,mid,r);//递归创建右子树
}
else {
node[p].lnd = node[p].rnd = -1;
}
}
void upData(int p) //每次插入或删除后的更新操作
{
if (node[p].cover > 0) //整条线段被覆盖
{
node[p].len = indexy[node[p].r] - indexy[node[p].l];
node[p].lines = 1;
node[p].lf = node[p].rf = 1;
}
else if (node[p].l == node[p].r - 1) //未被覆盖的元线段
{
node[p].lf = node[p].rf = 0;
node[p].len = node[p].lines = 0;
}
else { //未被覆盖的非元线段
int left = node[p].lnd;
int right = node[p].rnd;
node[p].lf = node[left].lf;
node[p].rf = node[right].rf;
node[p].len = node[left].len + node[right].len;
node[p].lines = node[left].lines + node[right].lines - node[left].rf*node[right].lf;
}
}
void Insert(int p,int l,int r) //插入线段
{
if (l <= node[p].l && node[p].r <= r)
node[p].cover ++;
else {
int mid = (node[p].l+node[p].r) >> 1;
if (mid > l)
Insert(node[p].lnd,l,r);
if (mid < r)
Insert(node[p].rnd,l,r);
}
upData(p);
}
void Delete(int p,int l,int r) //删除线段
{
if (l <= node[p].l && node[p].r <= r)
{
node[p].cover --;
}
else {
int mid = (node[p].l+node[p].r) >> 1;
if (mid > l)
Delete(node[p].lnd,l,r);
if (mid < r)
Delete(node[p].rnd,l,r);
}
upData(p);
}
bool cmp(const Cord &a,const Cord &b)
{
return a.x < b.x;
}
void init_index() //对纵坐标离散去重
{
sort(indexy+1,indexy+1+cnty);
int m = 1;
for (int i = 2; i <= cnty; i++)
{
if (indexy[i] != indexy[i-1])
{
m++;
indexy[m] = indexy[i];
}
}
cnty = m;
}
int Bi_search(int key) //二分查找 y 对应的离散坐标
{
int l = 1,r = cnty + 1,mid;
while (l < r)
{
mid = (l + r) >> 1;
if (indexy[mid] == key)
return mid;
if (indexy[mid] < key)
l = mid + 1;
else r = mid;
}
}
int main()
{
int i,j,left,right,prelen,prelines;
int x1,x2,y1,y2;
int ans;
while (scanf("%d",&n) != EOF)
{
for (i = 1;i <= n + n; i+=2)
{
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
cord[i].x = x1; cord[i].y1 = y1; cord[i].y2 = y2;
cord[i].f = true;
cord[i+1].x = x2; cord[i+1].y1 = y1; cord[i+1].y2 = y2;
cord[i+1].f = false;
indexy[i] = y1;
indexy[i+1] = y2;
}
sort(cord+1,cord+1+n+n,cmp);
cnty = n+n;
init_index();
cnt = 0;
Creat(root,1,cnty);
left = Bi_search(cord[1].y1);
right = Bi_search(cord[1].y2);
Insert(root,left,right);
prelen = node[root].len;
prelines = node[root].lines;
ans = prelen;
for (i = 2; i <= n+n; i++)
{
left = Bi_search(cord[i].y1);
right = Bi_search(cord[i].y2);
if (cord[i].f)
Insert(root,left,right);
else {
Delete(root,left,right);
}
ans += abs(prelen - node[root].len); //纵向周长增长量为前后两次被覆盖线段长度的改变量
ans += prelines*(cord[i].x - cord[i-1].x)*2; //横向周长的增长量为上一次区间个数乘2在乘横向长度
prelen = node[root].len;
prelines = node[root].lines;
}
printf("%d\n",ans);
}
return 0;
}