segment_tree.txt

线段树结构的代码

#include<stdio.h> 
#include<algorithm> 
using namespace std; 
struct NODE 
{ 
	int left, right, color; 
	NODE * lchild, * rchild; 
}; 
struct SEG 
{ 
	int left, right; 
	short color; 
}; 
NODE * pRoot; 
SEG * pData2; // 存放线段属性 
int * pData; // 存放无重复的坐标 
short Flag[8001]; 
// split node 
void split(NODE * pNode, int * pData, int li, int ri) 
{ 
	if(!pNode || ri - li <= 1) return; 
	pNode->lchild = new NODE; 
	pNode->lchild->color = -1; 
	pNode->lchild->lchild = pNode->lchild->rchild = NULL; 
	pNode->lchild->left = pData[li]; 
	pNode->lchild->right = pData[(li + ri) >> 1]; 
	pNode->rchild = new NODE; 
	pNode->rchild->color = -1; 
	pNode->rchild->lchild = pNode->rchild->rchild = NULL; 
	pNode->rchild->right = pData[ri]; 
	pNode->rchild->left = pData[(li + ri) >> 1]; 
	split(pNode->lchild, pData, li, (li + ri) >> 1); 
	split(pNode->rchild, pData, (li + ri) >> 1, ri); 
} 
// color the tree 
// result: maybe node[1,7].color = -1, 
// but its subnode: node[1, 5].color = 'b' and node[5,7].color = 'b' 
// use root-first traverse to join the segment together 
void colornode(NODE * pNode, int left, int right, int color) 
{ 
	if((pNode->left == left && pNode->right == right) || // 找到等长的（一定可以） 
// 找到一条比自己长的和自己同色的 
	(pNode->color == color)) 
	{ 
		pNode->color = color; 
		return; 
	} 
// color the root 
	if(pNode->color != -1) 
	{ 
		pNode->lchild->color = pNode->rchild->color = pNode->color; 
		pNode->color = -1; 
	} 
// split 
	if(right <= pNode->lchild->right) 
		colornode(pNode->lchild, left, right, color); 
	else if(left >= pNode->rchild->left) 
		colornode(pNode->rchild, left, right, color); 
	else 
	{ 
		colornode(pNode->lchild, left, pNode->lchild->right, color); 
		colornode(pNode->rchild, pNode->rchild->left, right, color); 
	} 
} 
// destroy the tree 
void destroy(NODE * pNode) 
{
	if(!pNode) return; 
	destroy(pNode->lchild); 
	destroy(pNode->rchild); 
	delete pNode; 
} 
// find a one-colored segment(use first root traverse) 
void find(NODE * pNode, short * pFlag, int & c) 
{ 
	if(pNode->color != -1) 
	{ 
		if(pNode->color != c) 
		{
			c = pNode->color; 
			pFlag[c]++; 
		} 
	} 
	else if(pNode->lchild) 
	{ 
		find(pNode->lchild, pFlag, c); 
		find(pNode->rchild, pFlag, c); 
	} 
	else c = -1; 
} 

int main() 
{
	int segs, xvalues, i, maxv, minv; 
	while(scanf("%d", &segs) == 1) 
	{ 
// allocate memory 
		pData = new int[2 * segs]; 
		pData2 = new SEG[segs]; 
		maxv = 0; minv = 0x7FFFFFFF; 
		// input data 
		for(i = 0; i < segs; ++i) 
		{ 
			scanf("%d%d%d", &pData2[i].left, &pData2[i].right, &pData2[i].color); 
			pData[2 * i] = pData2[i].left; 
			pData[2 * i + 1] = pData2[i].right; 
			if(pData2[i].left < minv) minv = pData2[i].left; 
			if(pData2[i].right > maxv) maxv = pData2[i].right; 
		} 
		sort(pData, pData + 2 * segs); 
		// make the x values distinct 
		for(xvalues = 0, i = 1; i < 2 * segs; ++i) 
		{ 
			if(pData[i] != pData[xvalues]) pData[++xvalues] = pData[i]; 
		} 
		// build the tree 
		pRoot = new NODE; 
		pRoot->left = minv; 
		pRoot->right = maxv; 
		pRoot->lchild = pRoot->rchild = NULL; 
		pRoot->color = -1; // change here to change the color of the whole tree 
		split(pRoot, pData, 0, xvalues); 
		delete [] pData; 
		// color the tree 
		for(i = 0; i < segs; ++i) 
		{ 
			colornode(pRoot, pData2[i].left, pData2[i].right, pData2[i].color); 
		} 
		delete [] pData2; 
// find the longest one 
		memset(Flag, 0, sizeof(Flag)); 
		int c = -1; 
		find(pRoot, Flag, c); 
		// output 
		for(i = 0; i <= 8000; ++i) if(Flag[i] > 0) printf("%d %d\n", i, Flag[i]); 
		printf("\n"); 
		// destroy the segtree 
		destroy(pRoot); 
	}
	return 1; 
}