noj 1044 类矩形并面积 线段树.txt

ACM资料大集合

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
//NOJ 1044 类矩形并面积 线段树
/*
4
1 4 3
2 7 2
6 9 4
9 10 3

6
1 5 10
3 8 8
4 7 20
8 9 40
10 14 30
12 13 15

输出
28
258
*/

#define NMAX 65000
typedef struct dis
{	//这里的ll和rr已经被离散了
	__int64 ll;
	__int64 rr;
	__int64 count;
	__int64 len;//测度
}dis;

typedef struct helloh
{
	__int64 high;//竖线的高度
	__int64 x;//竖线所在的水平位置
	bool add;//竖线是矩形的左边(true)，还是右边(false)
}helloh;

__int64 tth[NMAX*2];//已就high做升序排序，有重复的high
__int64 clh[NMAX*2];//剔除tth中有重复的high所得
helloh temph[NMAX*2];//已就x做升序排序
helloh srh[NMAX*2];//未经处理
dis hh[NMAX*4];//high的线段树结点

bool cmpx(struct helloh a,struct helloh b) {return a.x<b.x;}
bool cmph(__int64 a,__int64 b) {return a<b;}

__int64 findh(__int64 number,__int64 num)
{	//根据实际高度high，查找离散高度high
	int low,high,mid;
	low=1;high=num;
	mid=(low+high)/2;
	while(low<high)
	{	//经典的二分法查找
		if(clh[mid]==number) break;
		else if(clh[mid]<number) low=mid+1;
		else high=mid-1;
		mid=(low+high)/2;
	}
	return mid;
}

__int64 lisanh(__int64 num)
{
	__int64 i,j;
	for(i=1;i<=num;i++) {temph[i]=srh[i];tth[i]=srh[i].high ;}
	sort(temph+1,temph+1+num,cmpx);//temph按x升序排列
	sort(tth+1,tth+1+num,cmph);//tth按high升序排列
	clh[0]=0;
	clh[1]=tth[1];
	j=1;
	for(i=2;i<=num;i++)
	{	//clh中的high无重复，且升序排列，用于构造线段树
		if(tth[i-1] !=tth[i] ) clh[++j]=tth[i] ;
	}
	return j;
}

void create_tree(__int64 p,__int64 left,__int64 right)
{	//构造线段树
	__int64 mid;
	hh[p].ll=left;
	hh[p].rr=right;
	hh[p].count=0;
	if(left+1<right)
	{	//如果不是叶子结点，构造子结点
		mid=(left+right)/2;
		create_tree(2*p,left,mid);
		create_tree(2*p+1,mid,right);
	}
}

void update(int p)
{	//对测度进行维护
	if(hh[p].count == 0)
	{
		if(hh[p].ll+1 == hh[p].rr) hh[p].len=0;
		else hh[p].len=hh[2*p].len+hh[2*p+1].len;
	}
   	else hh[p].len=	clh[hh[p].rr]-clh[hh[p].ll];
}
void insert_tree(__int64 p,__int64 left,__int64 right)
{	//插入线段
	__int64 mid;
	//完全覆盖
	if(hh[p].ll==left&&hh[p].rr==right) hh[p].count++;
	else 
	{	//部分覆盖，往子节点插入线段
		mid=(hh[p].ll+hh[p].rr)/2;
		if(right<=mid) insert_tree(2*p,left,right);
		else if(left>=mid) insert_tree(2*p+1,left,right);
		else
		{
			insert_tree(2*p,left,mid);
			insert_tree(2*p+1,mid,right);
		}
	}
	update(p);
}

void delete_tree(__int64 p,__int64 left,__int64 right)
{	//删除线段
	__int64 mid;
	//完全覆盖
	if(hh[p].ll==left&&hh[p].rr==right) hh[p].count--;
	else 
	{	//部分覆盖，往子节点插入线段
		mid=(hh[p].ll+hh[p].rr)/2;
		if(right<=mid) delete_tree(2*p,left,right);
		else if(left>=mid) delete_tree(2*p+1,left,right);
		else
		{
			delete_tree(2*p,left,mid);
			delete_tree(2*p+1,mid,right);
		}
	}
	update(p);
}

__int64 get_count(__int64 p)
{	//得到根的测度
	int mm;
	if(hh[p].count>0) 
	{	//完全覆盖
		mm=clh[hh[p].rr]-clh[hh[p].ll];
		return mm;
	}
	else 
	{	//部分覆盖或不覆盖
		if(hh[p].ll+1==hh[p].rr) return 0;//叶子结点情况
		else 
		{	//内部结点情况
			mm=get_count(2*p)+get_count(2*p+1);//递归地查找子节点
			return mm;
		}
	}
}

__int64 init(__int64 num)
{	//对高度high进行离散处理，同时构造线段树
	__int64 hnum;
	hnum=lisanh(num);
	create_tree(1,0,hnum);
	return hnum;
}

__int64 solve(__int64 num,__int64 hnum)
{	//求面积
	__int64 i;
	__int64 sql=0;//面积
	__int64 lastx=0;//上一次竖线的水平位置
	__int64 lsh;//将实际高度转化后所得到的离散高度
	for(i=1;i<=num;i++)
	{
		lsh=findh(temph[i].high ,hnum);//求离散高度
		if(lastx!=0) sql+=hh[1].len * (temph[i].x-lastx); //get_count(1)*(temph[i].x-lastx);//求面积
//		if(lastx!=0) sql+=get_count(1) * (temph[i].x-lastx);
		if(temph[i].add==true) insert_tree(1,0,lsh);//如果是矩形的左边竖线，往线段树插入线段		
		else delete_tree(1,0,lsh);//否则，删除线段
		lastx=temph[i].x;//这个。。。。显然
	}
	return sql;
}
int main()
{
	__int64 num,ta,tb,th,i,j,hnum;
	while(scanf("%I64d",&num)!=EOF)
	{
		j=0;
		memset(tth,0,sizeof(tth));
		memset(clh,0,sizeof(clh));
		memset(temph,0,sizeof(temph));
		memset(srh,0,sizeof(srh));
		memset(hh,0,sizeof(hh));
		for(i=1;i<=num;i++)
		{
		scanf("%I64d%I64d%I64d",&ta,&tb,&th);
		srh[++j].add=true;
		srh[j].high=th;
		srh[j].x=ta;
		srh[++j].add=false;
		srh[j].high=th;
		srh[j].x=tb;
		}
		hnum=init(2*num);
		printf("%I64d\n",solve(2*num,hnum));
	}
	return 0;
}