3062601_ac_903ms_10188k.cpp

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

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

using namespace std;

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

node *root;

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

struct retnode
{
	__int64 l, r;
	__int64 h;
	int ll, rr;
}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,__int64 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);
		}
}

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

__int64 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)));
		}
	}
}

__int64 x[80001];

int main()
{
	int n, i, j, no;
	__int64 l, r, h, ans;

	scanf("%d",&n);
	for(i = 0; i < n; i++)
	{
		scanf("%I64d%I64d%I64d",&l,&r,&h);
		ret[i].l = l;ret[i].h = h;ret[i].r = r;
		pt[i*2].x = l;pt[i*2+1].x = r;
		pt[i*2].h = pt[i*2+1].h = h;
		pt[i*2].id = pt[i*2+1].id = i;
		ret[i].ll = ret[i].rr = -1;
	}
	root = INIT;
	no = 0;
	sort(pt,pt+n*2,cmp);
	for(i = 0; i < n*2; i++)
	{
		j = i;
		++no;
		x[no] = pt[i].x;
		while(j<n*2&&pt[j].x==pt[i].x)
		{
			if(ret[pt[j].id].ll==-1)
			{
				ret[pt[j].id].ll = no;
			}
			else
			{
				ret[pt[j].id].rr = no;
			}
			j++;
		}
		i = j-1;
	}
	create(root,1,no);
	for (i = 0; i < n; i++)
	{
		insert(root,ret[i].ll,ret[i].rr,ret[i].h);
	}
	ans = 0;
	for (i = 1; i < no; i++)
	{
		ans += (x[i+1]-x[i])*findH(root,i,i+1);
	}
	printf("%I64d\n",ans);
	return 0;
}