Description：

给定 $n$ 个闭区间 $[a_i,b_i]$ 和 $n$ 个整数 $c_i$ ，构造一个整数集合 $Z$ 使得 $\forall i\in[1,n]$ ， $Z$ 中满足 $a_i\le x \le b_i$ 的整数不少于 $c_i$ 个，求 $Z$ 的最小大小。

$1\le N \le 50000$

Solution：

设 $s[k]$ 表示 $Z$ 的前缀和，则有：

$s[b_i]-s[a_i]\ge c_i$

$s[k]\ge s[k-1]$

$s[k]-s[k-1]\le 1$

$s[0]=0$

跑差分约束即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n;

#define MAXN 50010

struct edge

{

	int to,nxt,w;

}e[MAXN * 10];

int edgenum = 0;

int lin[MAXN] = {0};

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

{

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

	return;

}

bool v[MAXN];

int d[MAXN];

int main()

{

	scanf("%d",&n);

	int maxd = 1;

	int a,b,c;

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

	{

		scanf("%d%d%d",&a,&b,&c);

		a += 2;b += 2;

		maxd = max(maxd,b);

		add(b,a - 1,-c);

	}

	for(int i = 2;i <= maxd;++i)

	{

		add(i,i - 1,0);

		add(i - 1,i,1);

		add(0,i,0);

	}

	add(0,1,0);

	memset(v,0,sizeof(v));

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

	queue<int> q;

	q.push(0);

	v[0] = true;

	d[0] = 0;

	while(!q.empty())

	{

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

		v[k] = false;

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

		{

			if(d[e[i].to] > d[k] + e[i].w)

			{

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

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

				{

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

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

				}

			}

		}

	}

	cout << d[maxd] - d[1] << endl;

	return 0;

}