Description：

给定 $n$ 个任务，第 $i$ 个任务在 $[L[i],R[i]]$ 间挑选一个时间完成，如果完成有 $c[i]$ 的收益。每天最多完成一个任务。请你安排任务的完成时间，使得总收益最大。

$1\le n \le 5000$

Solution：

建模和 $POI-Schools$ 一样，只是数据范围增大了，不能再直接跑费用流，由于区间内每个位置价值一样，所以可以用线段树优化建图，每个节点向儿子节点连容量为 $INF$ ，容量为 $0$ 的边，然后把区间建边拆为 $\log n$ 个区间即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n;

#define MAXN 5010

#define INF 0x3f3f3f3f

#define NAG 0xc0c0c0c0

struct edge

{

	int to,nxt,f,c;

}e[(MAXN * 2 + MAXN * 30 + MAXN * 30) * 2];

int edgenum = 0;

int lin[MAXN << 2];

void add(int a,int b,int f,int c)

{

	e[edgenum].to = b;e[edgenum].f = f;e[edgenum].c =  c;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].c = -c;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

int st,en;

struct node

{

	int lc,rc;

}t[MAXN << 2];

int ptr;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r){add(rt,en,1,0);return;}

	build(t[rt].lc,l,mid);add(rt,t[rt].lc,INF,0);

	build(t[rt].rc,mid + 1,r);add(rt,t[rt].rc,INF,0);

	return;

}

void addedge(int rt,int k,int L,int R,int v,int l,int r)

{

	if(L <= l && r <= R)

	{

		add(k,rt,1,v);

		return;

	}

	if(L <= mid)addedge(t[rt].lc,k,L,R,v,l,mid);

	if(R > mid)addedge(t[rt].rc,k,L,R,v,mid + 1,r);

	return;

}

int d[MAXN << 2],pre[MAXN << 2],rate[MAXN << 2];

bool v[MAXN << 2];

bool SPFA()

{

	memset(d,0xc0,sizeof(d));

	memset(pre,0,sizeof(pre));

	memset(rate,0x3f,sizeof(rate));

	queue<int> q;

	q.push(st);

	d[st] = 0;

	v[st] = true;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		v[k] = false;

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(d[e[i].to] < d[k] + e[i].c && e[i].f)

			{

				d[e[i].to] = d[k] + e[i].c;

				pre[e[i].to] = i;

				rate[e[i].to] = min(rate[k],e[i].f);

				if(!v[e[i].to])

				{

					v[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}

	return d[en] != NAG;

}

int flow()

{

	for(int i = en;i != st;i = e[pre[i] ^ 1].to)

	{

		e[pre[i]].f -= rate[en];

		e[pre[i] ^ 1].f += rate[en];

	}

	return rate[en] * d[en];

}

int EK()

{

	int ans = 0;

	while(SPFA())ans += flow();

	return ans;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d",&n);

	st = n + 1;en = st + 1;

	ptr = n + 2;

	build(root,1,4999);

	int l,r,v;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d%d",&l,&r,&v);--r;

		add(st,i,1,0);

		addedge(root,i,l,r,v,1,4999);

	}

	cout << EK() << endl;

	return 0;

}