题目分析

我们需要从给定的 $n$ 个区间 $[a_i, b_i]$ 中，每个区间至少选择 $c_i$ 个数，构造一个新的集合 $Z$。求在满足所有约束条件下，$Z$ 至少包含多少个数。

解题思路

1. 变量定义：

   • 设 $S_i$ 表示从 $1$ 到 $i$ 中被选出的数的个数。
   • 目标是求 $S_{50001}$（即整个范围内至少选多少个数）。

2. 约束条件：

   • 非递减约束：$S_i \geq S_{i-1}$，即从 $1$ 到 $i$ 选的数不会比 $1$ 到 $i-1$ 选的数少。 [ S_i \geq S_{i-1} ]
   • 相邻差约束：$S_i - S_{i-1} \leq 1$，即相邻位置最多选 $1$ 个数。 [ S_{i-1} \geq S_i - 1 ]
   • 区间约束：对于每个区间 $[a_i, b_i]$，至少选 $c_i$ 个数。 [ S_{b_i} \geq S_{a_i - 1} + c_i ]

3. 图的构建：

   • 将不等式转化为图的边：
     • $S_i \geq S_{i-1}$：从 $i-1$ 向 $i$ 连一条权值为 $0$ 的边。
     • $S_{i-1} \geq S_i - 1$：从 $i$ 向 $i-1$ 连一条权值为 $-1$ 的边。
     • $S_{b_i} \geq S_{a_i - 1} + c_i$：从 $a_i - 1$ 向 $b_i$ 连一条权值为 $c_i$ 的边。
   • 由于 $a_i$ 和 $b_i$ 可能从 $0$ 开始，我们统一将其 $+1$，避免与源点 $0$ 冲突。

4. 最长路求解：

   • 由于约束条件是 $S_i \geq S_j + w$，我们需要求最长路。
   • 从源点 $0$ 出发，计算到 $50001$ 的最长路，$S_{50001}$ 即为答案。

关键点

• 源点的可达性：
  • 由于约束 $S_i \geq S_{i-1}$ 保证了从 $0$ 出发可以遍历所有点，因此源点 $0$ 能到达所有边。
• 边界处理：
  • 将输入区间 $[a_i, b_i]$ 的 $a_i$ 和 $b_i$ 都 $+1$，避免 $0$ 下标问题。

复杂度分析

• 时间复杂度：
  • 最长路计算（如 SPFA）的最坏情况为 $O(nm)$，其中 $n$ 是点数，$m$ 是边数。
• 空间复杂度：
  • 存储图的边和距离数组，空间复杂度为 $O(n + m)$。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 50010, M = 150010;

int n;
int h[N],w[M],e[M],ne[M],idx;
int dist[N];
int q[N];
bool st[N];

void add(int a,int b,int c){
	e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
}

void spfa(){
	memset(dist,-0x3f,sizeof dist);
	int hh = 0, tt = 1;
	dist[0] = 0;
	q[0] = 0;
	st[0] = true;
	while(hh != tt){
		int t = q[hh++];
		if(hh == N) hh = 0;
		st[t] = false;
		for(int i = h[t]; ~i; i = ne[i]){
			int j = e[i];
			if(dist[j] < dist[t] + w[i]){
				dist[j] = dist[t] + w[i];
				if(!st[j]){
					q[tt++] = j;
					if(tt == N) tt = 0;
					st[j] = true;
				}
			}
		}
	}
}

int main(int argc, char** argv) {
	scanf("%d",&n);
	memset(h,-1,sizeof h);
	for(int i = 1; i <= 50001; i++){
		add(i-1,i,0);
		add(i,i-1,-1);
	}
	for(int i = 0; i < n; i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		a++; b++;
		add(a-1,b,c);
	}
	spfa();
	printf("%d",dist[50001]);
	return 0;
}