pku1177.cpp

PKU1177的源代码

//segment tree
///线段树 
///求边长
/////POJ1177
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_ELem = 40000;
const int MAX_Line = 10000;
struct Node{
	short left, right;
	bool coverd;
	short len, segment;
	short count;
	bool leftcover, rightcover;
	struct Node *lcd, *rcd;
	void Build(int, int);
	void Update();
	void Insert(int, int);
	void Delete(int, int);
}SegTree[MAX_ELem];
struct Node *root = &SegTree[0];
struct Data{
	short x, y1, y2;
	bool left;
}line[MAX_Line];
short node_val[MAX_Line];
int up = 0;

void Node::Build(int l, int r)
{
	left = l;
	right = r;
	coverd = 0;
	len = 0;
	segment = 0;
	count = 0;
	leftcover = rightcover = 0;
	if(r-l>1){
		int lenid = (l + r) / 2;
		lcd = &SegTree[++up];
		lcd->Build(l, lenid);
		rcd = &SegTree[++up];
		rcd->Build(lenid, r);
	}
}

void Node::Update()
{
	if(count>0){
		len = node_val[right] - node_val[left];
		segment = 1;
		leftcover = rightcover = 1;
	}else if(right-left==1){
		len = 0;
		segment= 0;
		leftcover = rightcover = 0;
	}else{
		len = lcd->len + rcd->len;
		segment = lcd->segment + rcd->segment;
		if(lcd->rightcover && rcd->leftcover)segment--;
		leftcover = lcd->leftcover;
		rightcover = rcd->rightcover;
	}
}

void Node::Insert(int l, int r)
{
	if(l<=node_val[left] && node_val[right]<=r){
		count++;
	}else{
		if(l<node_val[lcd->right]){
			lcd->Insert(l, r);
		}
		if(r>node_val[rcd->left]){
			rcd->Insert(l, r);
		}
	}
	Update();
}

void Node::Delete(int l, int r)
{
	if(l<=node_val[left] && node_val[right]<=r){
		count--;
	}else{
		if(l<node_val[lcd->right]){
			lcd->Delete(l, r);
		}
		if(r>node_val[rcd->left]){
			rcd->Delete(l, r);
		}
	}
	Update();
}

bool operator < (const Data &a, const Data &b)
{
	return a.x < b.x;
}

int abs(int a)
{
	return a>0 ? a : -a;
}

int main(int argc, char **argv) {
	//freopen("in","r",stdin);
	//freopen("out","w",stdout);
	int i, j, prev, ans, x1, y1, x2, y2, N;
	scanf("%d",&N);
	i = 0;
	for(j=0;j<N;j++){
		scanf("%d %d %d %d",&x1, &y1, &x2, &y2);
		line[i].x = x1; line[i].y1 = y1; line[i].y2 = y2; line[i].left = 1; node_val[i++] = y1;
		line[i].x = x2; line[i].y1 = y1; line[i].y2 = y2; line[i].left = 0; node_val[i++] = y2;
	}
	N *= 2;
	sort(line, line+N);
	sort(node_val, node_val+N);
	j = 1;
	for(i=1;i<N;i++){
		if(node_val[i]!=node_val[i-1]){
			node_val[j++] = node_val[i];
		}
	}
	up = 0;
	ans = 0;
	prev = 0;
	root->Build(0, j-1);
	for(i=0; i<N-1; i++){
		if(line[i].left){
			root->Insert(line[i].y1, line[i].y2);
		}else{
			root->Delete(line[i].y1, line[i].y2);
		}
		ans += root->segment*2*(line[i+1].x - line[i].x);
		ans += abs(root->len - prev);
		prev = root->len;
	}
	ans += root->len;
	printf("%d\n",ans);
	return 0;
}