#include <stdio.h>
#include <stdlib.h>

#define MAXN 50001

struct node
{
	int x, y, z;
}ivl[MAXN];
int n, ql, l;
int q[MAXN], temp[MAXN], f[MAXN] = {0};

int cmp( const void *a, const void *b )
{
	return ( ( struct node * )b )->x - ( ( struct node * )a )->x;
}

int main()
{
	int c, i, j, t, ty;
	scanf( "%d", &n );
	for ( i = 0; i < n; ++i )
		scanf( "%d%d%d", &ivl[i].x, &ivl[i].y, &ivl[i].z );
	qsort( ivl, n, sizeof( ivl[0] ), cmp );
	for ( ql = i = 0; i < n; ++i )
	{
		t = ivl[i].z; ty = ivl[i].y;
		for ( c = 0, j = ql-1; j >= 0 && c < t; --j )
			if ( ty >= q[j] )
				c++;
		l = 0;
		for ( j = ivl[i].x; c < t; ++j )
			if ( !f[j] )
			{
				temp[l++] = j;
				f[j] = 1; ++c;
			}
		for ( j = l-1; j >= 0; --j )
			q[ql++] = temp[j];
	}
	printf( "%d\n", ql );
	return 0;
}

分析二：差分约束系统，对于整数i,用a[i]表示i以前有多少个在集合s中，则对于区间[x,y]有a[y]-a[x]>=z，即a[x]-a[y]<=-z，在图中表示从y到x有一条权值为-z的边。另外结果还要满足a[i+1]-a[i]<=1,a[i]-a[i+1]<=0。分别表示从i到i+1有一条权为1的边和i+1到i有一条权为0的边。204ms A了

#include <stdio.h>
#include <string.h>
#define MAXN 50101

struct node
{
	int v, d, next; //
}pot[160000];
int g[MAXN], pl;
int dis[MAXN], visit[MAXN], queue[MAXN], used[MAXN];

int spfa( int n, int s ) //点的个数，源点，汇点
{
	int top, tail, u, v, k;
	memset( dis, 0x7f, sizeof( dis ) );
	memset( visit, 0, sizeof( visit ) );
	dis[s] = 0; top = 0; tail = 1;
	queue[0] = s; visit[s] = 1;
	while ( top != tail ) //循环队列
	{
		u = queue[top]; visit[u] = 0;
		top++;
		if ( top == n ) top = 0;
		for ( k = g[u]; k != -1; k = pot[k].next )
		{
			v = pot[k].v;
			if ( dis[v] - pot[k].d > dis[u] )
			{
				dis[v] = dis[u] + pot[k].d;
				if ( !visit[v] )
				{
					queue[tail] = v; visit[v] = 1;
					tail++;
					if ( tail == n ) tail = 0;
				}
			}
		}
	}
	return dis[n-1] - dis[s];
}

void addEdge( int u, int v, int w )
{
	pot[pl].next = g[u];
	g[u] = pl;
	pot[pl].v = v; pot[pl].d = w;
	pl++;
}

int main()
{
	int u, v, w, n, m = 0, mi = 0x7fffffff;
	memset( g, -1, sizeof( g ) );
	memset( used, 0, sizeof( used ) );
	pl = 0;
	scanf( "%d", &n );
	while ( n-- )
	{
		scanf( "%d%d%d", &u, &v, &w );
		v++;
		addEdge( u, v, -w );
		if ( v > m ) m = v;
		if ( u < mi ) mi = u;
	}
	for ( u = mi; u <= m; ++u )
	{
		addEdge( u, u+1, 0 );
		addEdge( u+1, u, 1 );
	}
	printf( "%d\n", -spfa( m+1, mi ) );
	return 0;
}

本来以为用离散化可以速度更快的，结果更慢了。。。。时间：329ms

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXN 50101

struct node
{
	int v, d, next; //
}pot[160000];
struct _Queue
{
	int value, label;
}q[MAXN];
int hs[MAXN], queue[MAXN], g[MAXN], l, pl; //hash, queue, length of queue
int dis[MAXN], visit[MAXN];

int cmp( const void *a, const void *b )
{
	return ( ( struct _Queue * )b )->value - ( ( struct _Queue * )a )->value;
}

void spfa( int n, int s ) //点的个数，源点，汇点
{
	int top, tail, u, v, k;
	memset( dis, 0x7f, sizeof( dis ) );
	memset( visit, 0, sizeof( visit ) );
	dis[s] = 0; top = 0; tail = 1;
	queue[0] = s; visit[s] = 1;
	while ( top != tail ) //循环队列
	{
		u = queue[top]; visit[u] = 0;
		top++;
		if ( top == n ) top = 0;
		for ( k = g[u]; k != -1; k = pot[k].next )
		{
			v = pot[k].v;
			if ( dis[v] - pot[k].d > dis[u] )
			{
				dis[v] = dis[u] + pot[k].d;
				if ( !visit[v] )
				{
					queue[tail] = v; visit[v] = 1;
					tail++;
					if ( tail == n ) tail = 0;
				}
			}
		}
	}
}

void addEdge( int u, int v, int w )
{
	pot[pl].next = g[u];
	g[u] = pl;
	pot[pl].v = v; pot[pl].d = w;
	pl++;
}

int HashKy( int u )
{
	if ( hs[u] != -1 ) return hs[u];
	q[l].value = u; q[l].label = l;
	hs[u] = l; l++;
	return l-1;
}

void hashAddEdge( int u, int v, int w )
{
	addEdge( HashKy( u ), HashKy( v ), w );
}

int main()
{
	int u, v, w, n;
	memset( hs, 0, sizeof( hs ) );
	memset( g, -1, sizeof( g ) );
	memset( hs, -1, sizeof( hs ) );
	pl = l = 0;
	scanf( "%d", &n );
	while ( n-- )
	{
		scanf( "%d%d%d", &u, &v, &w );
		hashAddEdge( v+1, u, -w );
	}
	qsort( q, l, sizeof( q[0] ), cmp );
	for ( u = 0; u < l-1; ++u )
	{
		addEdge( q[u].label, q[u+1].label, 0 );
		addEdge( q[u+1].label, q[u].label, q[u].value-q[u+1].value );
	}
	spfa( l, q[0].label );
	printf( "%d\n", dis[q[0].label]-dis[q[l-1].label] );
	return 0;
}