因为一行中如果断开的话就不算在同一行了，所以我们可以一行一行来考虑。
这样的话每层都会截出来一个最大的矩形，这有点向一个树形结构，可以用笛卡尔树
这里提一下，对于2312131这样的棋盘
三个1本来应该是同等级别的，但是在树上却有父子关系，因为它们之间的高的差为0
记f[i][j]表示以为代表的区域内放个棋的方案数，sz[u]表示以u为根的子树大小
显然，对于节点u，其矩阵的长为sz[u]，宽为h[u]-h[fa[u]]。
所以我们先跑一个树上背包，合并所有子树的情况，再单独讨论该节点的区域内的放置情况。 假设一共放个棋，在该区域内放个棋则方案数为
本来矩阵的长为sz[u]，但是要在子节点的范围内先放上j-k个棋，占用了j-k列，故还有sz[u]-j+k列能用来放