由于这道题至今无人改掉（其实是没人想改），我就不去说题解了，只说说我当时考试的思路。
按照套路，先想暴力，很明显，枚举矩形形状再去暴力查询是人人都想得到的，但是复杂度O(n^4)，而数据范围第一阶为n<=500，很明显，需要O(n^3)的复杂度，然后想到了类似扫描线的打发，完善后成功骗到30分。
我们可以先确定一下整个矩形的宽，然后去O(n^2)枚举宽所在的位置，再不断更新当前矩形的上边界的行数的最大值，我们就可以成功的在O(n^3)内完成答案统计。
至于k<=3的步骤分，我是真没想出来……
原文：http://www.cnblogs.com/liutianrui/p/7615794.html