P10561 [ICPC 2024 Xi'an I] Smart Quality Inspector

Ella 有一家工厂。一天，她的工厂面临产品质量检查。 她的工厂有 $N$ 条生产线。在这 $N$ 条生产线中，有 $N-K$ 条是合格的，另外 $K$ 条是不合格的。第 $i$ 条（$1\leq i\leq K$）不合格生产线的罚款为 $i$ 元。 这里有 $M$ 名质量检查员。对于第 $j$ 名（$1\leq j\leq M$）质量检查员，他将检查从第 $l_i$ 条到第 $r_i$ 条的生产线，并在其中找到罚款最高的不合格生产线，然后将此罚款施加给 Ella。 Ella 不想收到太多罚款，所以她决定重新编号这 $N$ 条生产线以使收到的罚款最少。请帮助她。 简单来说： 你有一个长度为 $N$ 的序列 $A$，$A=[1,2,3,...,K,0,0,0,...,0]$。这里 $N,K$ 已知。 有 $M$ 对整数，每对由两个数字 $l_i,r_i$ 组成。 你需要重新排列序列 $A$ 以最小化以下值： $$\sum_{i=1}^M \max_{j=l_i}^{r_i} (A_{j})$$

无

无

（由 ChatGPT 4o 翻译）