有一个 n× m 的矩形，矩形中的每个点初始值为 0 ，将每一行都分为若干块，每一块中，最多有一个点可以变化成 1 ，评判一个矩形质量的计算为：每一列中 1 的数量的平方和。 例如：一个 3× 5 的矩形，第一行分成 [ 1, 2],[ 3, 4],[ 5, 5] 三块，第二行分成 [ 1, 2],[ 3, 5] 两块，第三行分成 [ 1, 3],[ 4, 5] 两块。 那么，下述两种挑点转化成 1 的方案都是合法的： 1 0 1 0 1\ 1 0 1 0 0\ 0 0 1 0 1 1 0 1 0 1\ 1 0 0 0 1\ 1 0 0 0 1 而下述方案是不合法的 1 0 1 0 1\ 1 0 1 0 0\ 1 0 1 0 1 由于 ( 3, 1) 这个点和 ( 3, 3) 这个点属于同一块，而一块中最多只能出现一个 1 ，所以不合法。 对于上述两种合法方案而言，第一种方案的矩形质量为： 2 ^ 2+ 3 ^ 2+ 2 ^ 2= 17 第二种方案的矩形质量为： 3 ^ 2+ 1 ^ 2+ 3 ^ 2= 19 其中，第二种方案的矩形质量是当前分块状态下的最大值，该变化方案称之为最佳配置，显然，最佳配置的方案可能不唯一，但是，同为最佳配置的矩形质量一定是相同且最大的。 那么，对于一种矩形分块的情况，它最佳配置下的矩形质量可以达到多少？
对于每组测试数据，第一行输入两个正整数 n, m( 1≤ n, m≤ 100) ，代表矩形的行、列长度。 接下去输入 n 行的分块信息，对于矩形的第 i 行而言，第一行输入一个正整数 k( 1≤ k≤ m) ，代表第 i 行分成了 k 块。 接下去 k 行，每行两个正整数 l, r( 1≤ l≤ r≤ m) ，代表第 i 行的某一分块的起点和终点(闭区间)。 数据保证，每一行的分块区间一定不重叠，且覆盖了 m 列。
一行输出一个整数代表某一种最佳配置下的矩形质量。
3 5 3 1 2 3 4 5 5 2 1 2 3 5 2 1 3 4 5
19
考点：贪心
数据规模 n ≤ 100 ｜ 限制 1 秒 / 64MB ｜ 标准输入输出
推荐方向：贪心
本题切入点
每一行各自独立：每块只能选一个点变 1，为了让列平方和最大，贪心地让各行的选择尽量分散到不同列。
每一步都取当前最优，靠问题性质保证局部最优能拼成全局最优。
思路框架（贪心 通法 · 非本题专属）
实现要点：贪心题关键在于排序规则：按什么关键字排序决定了策略是否正确。
复杂度：时间 O(n log n)（含排序） ｜ 空间 O(1) ~ O(n)
该范式的通法易错点
对照本题
样例 1
3 5 / 3 / 1 2 / 3 4 / 5 5 / 2 / 1 2 / 3 5 / 2 / 1 3 / 4 519解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：2024年秋招-贝壳找房-Java工程师-第二批笔试；2024年秋招-贝壳找房-C++工程师-第二批笔试；2024年秋招-贝壳找房-机器学习/数据挖掘工程师-第二批笔试。