题解

思路

平方函数鼓励把选择集中到同一列。对一组端点都在 $[l,r]$ 内的区间，可以钦定优先级最高的一列 $k$，让所有经过 $k$ 的区间都选择 $k$；其余区间完全落在左右两侧，形成两个独立子问题。

做法

子任务 1：枚举选点

递归枚举每个输入区间选择的列，维护各列数量并计算质量，取最大值。

子任务 2：直接统计区间 DP

设 $f_{l,r}$ 为只考虑端点均在 $[l,r]$ 中的输入区间时的最大质量。枚举最高优先级列 $k$，再扫描全部输入区间，统计端点在 $[l,r]$ 且经过 $k$ 的区间数 $c$：

$$f_{l,r}=\max_{k=l}^{r}\{f_{l,k-1}+c^2+f_{k+1,r}\}.$$

子任务 3：二维前缀和

令 $b_{x,y}$ 为输入中区间 $[x,y]$ 的数量。固定 $l,r,k$ 时，所需的 $c$ 是

$$\sum_{x=l}^{k}\sum_{y=k}^{r}b_{x,y},$$

这是二维矩形和，可在预处理二维前缀和后 $O(1)$ 求出。再按区间长度递增完成上述 DP。

复杂度

满分算法时间复杂度 $O(nm+m^3)$，空间复杂度 $O(m^2)$。