关于题目的checker

Water__Problem @ 2026-01-21 19:19:42

by s4CRIF1CbUbbL3AtIAly @ 2026-01-21 19:25:42

分治，每次复杂度是长边乘短边加短边平方，所以总复杂度 O(nm\log nm)。

by Water__Problem @ 2026-01-21 19:29:56

@s4CRIF1CbUbbL3AtIAly 好像是对的/bx/bx/bx

by Water__Problem @ 2026-01-21 19:30:28

此帖结

by s4CRIF1CbUbbL3AtIAly @ 2026-01-21 19:31:56

具体做法的话就是你在分治的时候会有一条分隔线，这条线会你要统计的矩形的壳子变成两边独立的 C 形，我们要对其计数。不妨假设我们现在是竖着切开的。

那么我们要对于任意两行 x_1,x_2 数有多少个 y 满足它们确定出的那个 C 形合法。不妨假设我们现在只看左边的 C 形，那么怎么描述合法呢？记 x 这一行从分割线往左延伸能到的最靠左的合法位置是 lim_x，那么显然要有 y\ge lim_{x_1},y\ge lim_{x_2}。

另外 C 的那条竖边也要合法，那么记 down_{x,y} 表示从这个位置竖着向下延伸能到的位置，那么还有一条限制就是 down_{x_1,y}\ge x_2。

考虑对于一对 (x_1,x_2,y) 要求 lim_{x_1}\le lim_{x_2}，这样我们就只有两条限制了，枚举 x_1 和 y 之后可以用桶记下来每个 y 能够贡献的最大范围，然后再扫一遍 x_2 计算答案，然后只在 lim_{x_2}\ge lim_{x_1} 的时候统计上即可。

by nullqtr_pwp @ 2026-01-21 19:39:50

@s4CRIF1CbUbbL3AtIAly 小 C 和小 H

by lucasaa @ 2026-01-21 19:47:43

%%%

by lucasaa @ 2026-01-21 19:48:30

Water__Problem怎么还在lh我