3062425_mle.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>
#define INIT (node *)malloc(sizeof(node))

using namespace std;

struct node 
{
	int h;
	int l, r;
	node *left, *right;
};

node *root;

struct point 
{
	int h;
	int x;
}pt[80001];

struct retnode
{
	int l, r;
	int h;
}ret[40001];

node *create(node *s,int l,int r)
{
	int mid;
	node *p, *q;
	
	s->h = 0;
	s->l = l,s->r = r;
	if(l+1==r)
	{
		s->left = NULL;
		s->right = NULL;
		return s;
	}
	mid = (l+r)/2;
	p = INIT,q = INIT;
	s->left = create(p,l,mid);
	s->right = create(q,mid,r);
	return s;
}

bool cmp(point a,point b)
{
	return a.x < b.x;
}

void insert(node *s,int l,int r,int h)
{
	int mid;

	if(s->l==l&&s->r==r)
	{
		s->h = (s->h>h?s->h:h);
		return ;
	}
	mid = (s->l+s->r)/2;
	if(r<=mid)
		insert(s->left,l,r,h);
	else
		if(l>=mid)
			insert(s->right,l,r,h);
		else
		{
			insert(s->left,l,mid,h);
			insert(s->right,mid,r,h);
		}
}

int max(int a,int b)
{
	return a > b ? a : b;
}

int findH(node *s,int l,int r)
{
	int mid;

	if(s->l==l&&s->r==r)
		return s->h;
	mid = (s->l+s->r)/2;
	if(r<mid)
	{
		return max(s->h,findH(s->left,l,r));
	}
	else
	{
		if(l>=mid)
		{
			return max(s->h,findH(s->right,l,r));
		}
		else
		{
			return max(s->h,max(findH(s->left,l,mid),findH(s->left,l,mid)));
		}
	}
}

int main()
{
	int n, i, l, r, h;
	int min, max, ans;

	min = 2100000000;max = -1;
	scanf("%d",&n);
	for(i = 0; i < n; i++)
	{
		scanf("%d%d%d",&l,&r,&h);
		if(l < min)	min = l;
		if(r > max)	max = r;
		ret[i].l = l;ret[i].h = h;ret[i].r = r;
		pt[i].x = l;pt[i+n].x = r;
		pt[i].h = pt[i+n].h = h;
	}
	root = INIT;
	create(root,min,max);
	sort(pt,pt+n*2,cmp);
	for (i = 0; i < n; i++)
	{
		insert(root,ret[i].l,ret[i].r,ret[i].h);
	}
	n <<= 1;
	ans = 0;
	for (i = 1; i < n; i++)
	{
		if(pt[i].x!=pt[i-1].x)
		{
			ans += (pt[i].x-pt[i-1].x)*findH(root,pt[i-1].x,pt[i].x);
		}
	}
	printf("%d\n",ans);
	return 0;
}