为什么爆成这样还要写记录。abc420&&cf2133
省流：abc 没质量；cf 没实力。AT_abc420_f kirinuki
你早说你是 \(O(NM)\) 的不就行了嘛。
一眼感觉不太好计数，但是 \(NM \le 5\times 10^6\) 就很有意思。直接上分治，我们去分治列，则现在只需要解决 \(l_y \in \land r_y \in (mid,r]\) 时的计数。去枚举 \(l_x=i\)，记 \(nxt_{i,j}\) 表示第 \(i\) 列第 \(j\) 行能够向下拓展的最远距离，满足中间所有点都是 .。那么分治枚举 \(l_y = y\) 时，可能的矩形宽不会超过 \(\min\limits_{k=y}^{mid}nxt_{k,i}\)，因为一旦宽比这个大就说明至少存在一列包含了至少一个 #。然后就是板子了，可以通过双指针找到 \(y'\)，满足对于所有 \(r_y \in (mid,y']\)，都有 \(\min\limits_{k=mid+1}^{r_y}nxt_{k,i} \ge \min\limits_{k=y}^{mid}nxt_{k,i}\)，而 \(r_y \in (y',r]\) 都有 \(\min\limits_{k=mid+1}^{r_y}nxt_{k,i} < \min\limits_{k=y}^{mid}nxt_{k,i}\)。记 \(mi=\min\limits_{k=y}^{mid}nxt_{k,i}\)，那么 \(r_y \in (mid,y']\) 时的贡献就是所有长在区间 \(\)，宽在区间 \(\) 且面积不超过 \(K\) 的矩形数量。这个满足：\(cnt=\sum\limits_{i=mid+1-y+1}^{y'-y+1}\min(mi,\lfloor\frac{K}{i}\rfloor)\)，差分一下就只需要维护 \(\sum\limits_{i=1}^{a}\min(b,\lfloor\frac{K}{i}\rfloor)\)。由于 \(a \le m,b\le n\)，所以预处理的时间复杂度 \(O(NM)\)。对于 \(r_y\in (y',r]\) 的情况，相当于是在枚举 \(r_y=y\) 维护 \(l_y \in \)，所以倒着跑一遍就行了。
时间复杂度 \(O(NM\log M)\)，但是由于 \(\min(N,M)\le \sqrt{NM}\)，所以分治大小较小的那边可以做到 \(O(NM\log \sqrt{NM})\)。代码 \(to_{i,j}\) 就是 \(nxt_{i,j}\)。
il void work(int l,int r){ if(l>r) return ; if(l==r){ for(re int i=1,j=0;im>>K; for(re int i=1;i 热心回复！ 这个有用。 不错，里面软件多更新就更好了 谢谢楼主提供！ 不错，里面软件多更新就更好了 谢谢楼主提供！ 分享、互助 让互联网精神温暖你我 前排留名，哈哈哈 感谢分享，学习下。 热心回复！ 用心讨论，共获提升！ 鼓励转贴优秀软件安全工具和文档！ 感谢分享，学习下。 谢谢分享，试用一下 用心讨论，共获提升！ 用心讨论，共获提升！ 用心讨论，共获提升！ 这个好，看起来很实用 热心回复！
页:
[1]
2