题解

思路

把位置看成顶点，把每条限制 $(A_i,B_i,C_i)$ 看成权为 $C_i$ 的边。

做法

令 $X_v$ 为顶点 $v$ 的所有关联边权最小值，则必须有 $P_v\le X_v$。按 $k=N,N-1,\ldots,1$ 决定数值 $k$ 放在哪个尚未使用的位置：若权为 $k$ 的边不少于两条，它们必须拥有同一个公共端点且只能把 $k$ 放在那里；若恰有一条边，则从两个满足 $X_v\ge k$ 的端点中选择；若没有这种边，则可从所有尚未使用且 $X_v\ge k$ 的顶点中任选。每步把可选位置数乘入答案并删除实际选中的一个位置，若没有可选位置则答案为零。

复杂度

用按 $X_v$ 分桶的双向链表维护当前可用顶点，并按边权分组检查公共端点，总时间复杂度为 $O(N+M)$，空间复杂度为 $O(N+M)$。