#include <iostream>
#include <algorithm>
using namespace std;

const int SIZE = 40002;
int pos[SIZE * 2], n, tmp[SIZE * 2];

typedef struct node
{
	int s, e;
	int h;

	node()
	{ s = e = h = 0; }
}Node;

Node points[SIZE];

class SegmentTree
{
public:
	Node nodes[SIZE * 6];
public:
	void buildtree( int, int, int );
	void update( int, int, int, int );
	__int64 getresult( int, int, int, int );
};

void SegmentTree::buildtree( int root, int s, int e )
{
	nodes[root].s = s;
	nodes[root].e = e;
	nodes[root].h = 0;

	if( e - s  > 1 )
	{
		int mid = ( s + e ) / 2;
		buildtree( root * 2, s, mid );
		buildtree( root * 2 + 1, mid, e );
	}
}

void SegmentTree::update( int root, int s, int e, int h )
{
	if( nodes[root].h > h )
		return;

	if( s <= nodes[root].s && nodes[root].e <= e )
	{
		nodes[root].h = h;
		return;
	}

	if( nodes[root].e - nodes[root].s == 1 )
		return;

	int mid = ( nodes[root].s + nodes[root].e ) / 2;
	if( s < mid )
		update( root * 2, s, e, h );
	if( mid < e )
		update( root * 2 + 1, s, e, h );
}

__int64 SegmentTree::getresult( int root, int s, int e, int maxv )
{
	if( maxv < nodes[root].h )
		maxv = nodes[root].h;

	if( nodes[root].e - nodes[root].s == 1 )
		return (__int64) maxv * ( pos[nodes[root].e] - pos[nodes[root].s] );

	__int64 r = 0;
	int mid = ( nodes[root].s + nodes[root].e ) / 2;
	if( mid <= s )
		r += getresult( root * 2 + 1, s, e, maxv );
	else if( mid >= e )
		r += getresult( root * 2, s, e, maxv );
	else
	{
		r += getresult( root * 2, s, mid, maxv );
		r += getresult( root * 2 + 1, mid, e, maxv );
	}

	return r;
}

int find( int n, int v )
{
	int low = 1, high = n, mid;

	while( low < high )
	{
		mid = ( low + high ) / 2;
		if( pos[mid] < v )
			low = mid + 1;
		else
			high = mid;
	}
	
	return high;
}

SegmentTree tree;


int main()
{
	int num = 1, i, count;
	scanf( "%d", &n );
	for( i = 1; i <= n; i++ )
	{
		scanf( "%d%d%d", &points[i].s, &points[i].e, &points[i].h );
		tmp[num++] = points[i].s;
		tmp[num++] = points[i].e;
	}

	num--;
	sort( tmp + 1, tmp + 1 + num );
	pos[1] = tmp[1];
	for( i = count = 2; i <= num; i++ )
	{
		if( tmp[i] != tmp[i - 1] )
			pos[count++] = tmp[i];
	}

	count--;
	tree.buildtree( 1, 1, count );
	for( i = 1; i <= n; i++ )
	{
		int l = find( count, points[i].s );
		int r = find( count, points[i].e );
		
		tree.update( 1, l, r, points[i].h );
	}

	printf( "%I64d\n", tree.getresult( 1, 1, count, 0 ) );

	return 0;
}

• 注意：数组开小了也会WA。。 (0) liao14 2008-11-17 13:33:13
  • Re:注意：数组开小了也会WA。。 (0) silence_nenu 2009-10-22 01:00:27
  • Re:注意：数组开小了也会WA。。 (0) silence_nenu 2009-10-22 01:00:42