P4229 某位歌姬的故事

一个经典题。

首先进行离散化。我们容易发现若位置 $x$ 被 $(l_i,r_i,m_i),(l_j,r_j,m_j)$ 甚至更多限制同时覆盖。若 $m_i\neq m_j$，那么我们只需要保留 $\max(m_i,m_j)$ 的限制即可；若 $m_i=m_j$，那么我们需要单独拿出来尝试求。所以说我们按照 $m_i$ 可以分为若干不相交的连续区间，这些区间的答案都是独立的，最后乘起来就好了。