picture(线段树测度，独立线段数).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

struct node {
	int l, r;//左右端点
	int il, ir;
	node * pl, * pr;//左右子树
	int len;//测度
	int cover;//完全覆盖线段数
	int lines;//独立线段数
	int lbd, rbd;//左右端点覆盖
}mem[40000];
int mem_pos;

struct line {
	int x,y1,y2;
	int flag;
	bool operator < (const line & tt ) const {
		if(x != tt.x) {
			return x < tt.x;
		}
		return flag > tt.flag;//当x轴相同，即重复边，先加后减
	}
}list[11000];

int yaxis[11000];

node *
new_node()
{
	node * pt = &mem[mem_pos ++];
	memset(pt,0,sizeof(node));
	return pt;
}

void
cal_len(node * root)//计算测度
{
	root ->len = 0;
	if(root ->cover > 0) {
		root ->len = root ->r - root ->l;
	}
	else {
		if(root ->pl && root ->pr) {
			root ->len = root ->pl ->len + root ->pr ->len;
		}
	}
}

void
cal_line(node * root)//计算独立线段数
{
	root ->lbd = root ->rbd = root ->lines = 0;
	if(root ->cover > 0) {
		root ->lbd = root ->rbd = root ->lines = 1;
	}
	else {
		if(root ->pl && root ->pr) {
			root ->lbd = root ->pl ->lbd;
			root ->rbd = root ->pr ->rbd;
			root ->lines = root ->pl ->lines + root ->pr ->lines
						- (root ->pl ->rbd * root ->pr ->lbd); 
		}
	}
}

node *
make_tree(int axis[], int il, int ir)
{
	node * root = new_node();
	root ->l = axis[il];//依照数组造树
	root ->r = axis[ir];
	root ->il = il;
	root ->ir = ir;
	if(ir - il > 1) {
		int mid = (il+ir)/2;
		root ->pl = make_tree(axis, il, mid);
		root ->pr = make_tree(axis, mid, ir);
	}
	return root;
}

void
update(node * root, line e)
{
	if(e.y1 <= root ->l && root ->r <= e.y2) {//覆盖子区间
		root ->cover += e.flag;
	}
	if(root ->ir - root ->il > 1) {
		int mid = (root ->il + root ->ir)/2;
		if(e.y1 < yaxis[mid]) {
			update(root ->pl, e);
		}
		if(yaxis[mid] < e.y2) {
			update(root ->pr, e);
		}
	}
	cal_len(root);
	cal_line(root);
}

int 
main()
{
	int t,n,i;
	int ls;
	int x1,x2,y1,y2;
	int sum;
	while(scanf("%d", &n)==1) {
		ls = 0;
		mem_pos = 0;
		sum = 0;
		for(i=0;i<n;i++) {
			scanf("%d %d %d %d", &x1,&y1,&x2,&y2);
			list[ls].x = x1;
			list[ls].y1 = y1;	list[ls].y2 = y2;
			list[ls].flag = 1;
			list[ls+1].x = x2;
			list[ls+1].y1 = y1;	list[ls+1].y2 = y2;
			list[ls+1].flag = -1;
			yaxis[ls] = y1;
			yaxis[ls+1] = y2;

			ls += 2;
		}
		sort(yaxis, yaxis+ls);
		sort(list, list+ls);
		
		int preLen = 0, preLines = 0;
		node * root = make_tree(yaxis, 0, ls-1);
		for(i=0;i<ls;i++) {
			update(root, list[i]);
			sum += abs(root ->len - preLen);
			sum += 2 * preLines * (list[i].x - list[i-1].x);
			//printf("(%d,%d) %d (%d,%d)\n", root->len, root->lines, sum, preLen,preLines);
			preLen = root ->len;
			preLines = root ->lines;
		}
		printf("%d\n", sum);
	}
}