\(\text{Solution:}\)
首先一个显然的结论是让每一列的 \(1\) 的个数越多越好。
证明： \((a+b)^2>a^2+b^2.\)
于是我们应该考虑的是怎么让一列的数的和最大。
发现我们可以合并两个区间的答案，而数据范围这么小，很容易让人想到 \(O(n^3)\) 的算法。
试着考虑区间 \(dp:\) 设 \(f[l][r]\) 表示区间 \([l,r]\) 的最大平方和。
然后会发现：这个端点可能跨越了一些段，导致很难转移。
于是我们更改一下：设 \(f[l][r]\) 为所有端点都在 \([l,r]\) 内的线段组合的最大平方和。那么转移就是：
\[f[l][r]=\max\{ f[l][k-1]+f[k+1][r]+sum^2[l][r][k]\}
\]
其中 \(sum[l][r][k]\) 代表区间 \([l,r]\) 中跨越 \(k\) 的线段个数。
考虑怎么处理这个东西：发现对于一个线段 \(l,r,k\in[l,r],[1,l-1]\cup [r+1,m]\) 内的端点才会有影响。
考虑一个以 \(l\) 为横坐标 \(r\) 为纵坐标的坐标系，那影响的范围就是一个矩阵。二维前缀和即可。
有一种神奇的写法：先前缀做出一条线的和，再扫成矩阵的面积。
#include<bits/stdc++.h>
using namespace std;
int n,m,f[101][101];
int sum[101][101][101];
struct line{int l,r;}p[101][101];
int cnt[101];
inline int Max(int x,int y){return x>y?x:y;}
int main(){
freopen("111.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
int x;
scanf("%d",&x);
for(int j=1;j<=x;++j){
++cnt[i];
scanf("%d%d",&p[i][cnt[i]].l,&p[i][cnt[i]].r);
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=cnt[i];++j){
int l=p[i][j].l;
int r=p[i][j].r;
for(int k=l;k<=r;++k)sum[l][r][k]++;
}
}
for(int k=1;k<=m;++k){
for(int i=1;i<=m;++i){
for(int j=1;j<=m;++j){
sum[i][j][k]+=sum[i][j-1][k];
}
}
for(int i=m;i;--i){
for(int j=1;j<=m;++j){
sum[i][j][k]+=sum[i+1][j][k];
}
}
}
// for(int k=1;k<=m;++k){
// printf("%d:\n",k);
// for(int i=1;i<=m;++i){
// for(int j=1;j<=m;++j)printf("%d ",sum[i][j][k]);
// puts("");
// }
// }
for(int i=1;i<=m;++i)f[i][i]=sum[i][i][i]*sum[i][i][i];
for(int len=2;len<=m;++len){
for(int l=1;l<=m-len+1;++l){
int r=l+len-1;
for(int k=l;k<=r;++k){
f[l][r]=Max(f[l][r],f[l][k-1]+f[k+1][r]+sum[l][r][k]*sum[l][r][k]);
}
}
}
printf("%d\n",f[1][m]);
return 0;
}