RT

窝看到有那么多假跳蚤，决定要来拯救跳蚤王国！

题目可以见nodgd的网盘。

窝感觉这个题目很好玩的说。网上暂时还没题解的样子。。

我口胡了一个比较暴力但能过的做法。。 如果有另外的解法欢迎在下面与我交流。

首先观察到n=30 这是非常经典的meet in the middle的数据规模，然后我们发现这完全不能meet in the middle。。

然后我们考虑暴力，一个最简单的暴力是枚举点的位置，枚举每条边延伸的长度，这样的复杂度是n^6*m^6 可以过30分了耶！

我们发现其实木有必要枚举每条边延伸的长度，判断一下每个点所在的位置，用乘法加法搞一搞就出来了（雾），这样我们就可以做到n^3m^3啦！

这个做法（我自以为）优化起来是非常麻烦的，另外30^6似乎小于100000^2了呢，窝没写过这个做法不知道能不能过。。

窝来讲一个比较简单的做法。。

考虑枚举两个点，这样是n^4（为了方便看做n=m），再枚举两个点向右延伸出多长，我们令A点为(x1,y1)，B点为(x2,y2)，为了方便我们令x1>x2 或者 x1=x2且y1>y2。 然后我们发现我们只需找到一个C点(x3,y3)(x3>x1 || x3==x1 && y3>y1)就能很轻松的计算出答案来。 这样是n^8。

考虑优化这个做法，实际上我们枚举A点与A点向右延伸多少之后(n^3)，假如没有B点所在的“L”型的限制，那么我们是可以统计出C点为端点的“L”型的个数(n^2)。我们再看看B对C的影响，只有可能是对于某些C点往上延伸的长度受到限制，我们从大到小枚举x2(n)，再将整个矩阵扫一遍，表示如果该列往上限制是x2，那么会减少多少个“L”型(n^2)，最后在统计答案的时候，我们只需要枚举B所在的点和向右延伸出去的长度，就可以在O(1)的时间内统计答案。

至此，总的复杂度为O(n^6)

观察本题性质，实际上可能会对答案有贡献的A,B仅有n^6/8对。所以我们就可以轻松愉悦的通过本题啦！

现在问题来了，这题并不是seraja或者陈老师出的，那么显然应该有比较好看不那么卡时的做法咯。

我们考虑“再将整个矩阵扫一遍，表示如果该列往上限制是x2，那么会减少多少个“L”型(n^2)”这一个问题，发现只需要将A点与B点的行固定住(n^2)，就能预处理出这个玩意儿(n^2)，因此这一部分我们可以在n^4完成。

那么还剩下最后一个问题，就是在枚举B的时候，怎么才能做到n^2呢，一个显然的做法是我们只需要枚举B的位置，并不需要枚举它能延伸出去的长度，那么这个位置对答案的贡献是 A*((ans-a1)+(ans-a1-a2)+...+(ans-a1-a2-..-ak))这个显然可以记录前缀和来O(1)实现！

至此，总复杂度为O(n^5)

对于一个有常数巨大debuff的人还是在BZOJ现有AC人数里排到rank1啦~ 可见这个做法还是比较优美的。。