为什么爆成这样还要写记录。abc420&&cf2133

省流：abc 没质量；cf 没实力。

AT_abc420_f kirinuki

你早说你是 \(O(NM)\) 的不就行了嘛。
一眼感觉不太好计数，但是 \(NM \le 5\times 10^6\) 就很有意思。直接上分治，我们去分治列，则现在只需要解决 \(l_y \in [l,mid]\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']\) 时的贡献就是所有长在区间 \([mid+1-y+1,y'-y+1]\)，宽在区间 \([1,mi]\) 且面积不超过 \(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 [y',mid]\)，所以倒着跑一遍就行了。
时间复杂度 \(O(NM\log M)\)，但是由于 \(\min(N,M)\le \sqrt{NM}\)，所以分治大小较小的那边可以做到 \(O(NM\log \sqrt{NM})\)。代码 \(to_{i,j}\) 就是 \(nxt_{i,j}\)。
[code]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