Luogu-P5046 Ynoi2019 模拟赛 Yuno loves sqrt technology I
数据范围和实现指出本题复杂的几乎不可能带 \(\log\)，考虑一个分块做法。
对于散块可以直接每个块内点对求出是否有逆序对，然后做二维前缀和。
不带 \(\log\) 的逆序对处理方法只能是预先排好序然后归并，这样瓶颈是没有 \(\log\) 的。所以可以对每个块先排好序，容易归并处理出第 \(i\) 个块与位置 \(j\) 的逆序对个数，做一个前缀和就行了。
还剩下两个散块的贡献，这部分直接拿出来再归并一次。
提交记录：Submission - Luogu
CodeForces-1392I Kevin and Grid *3300
这题课件上先给了平面图欧拉公式：\(|V|-|E|+|F|=2\)，联通块个数公式：\(|C|=|V|-|E|+|F|-1\)。
\(|V|\) 和 \(|E|\) 都是非常好算的，大概是把两个桶函数卷积，\(|V|\) 就是直接卷，\(|E|\) 就是相邻两个都小于或大于等于才有贡献，取 \(\max\) 或 \(\min\) 就行了。
考虑算 \(|F|\)，发现题目中小于的权值减去大于等于的权值以及是否和边界相邻权值不同是很突兀的，除了外面无限延伸的面以外，如果某个连通块内还有其他连通块，那么对 \(|F|\) 而言增加了 \(1\)，对被包含的连通块而言也增加了 \(1\)，二者异色是减法关系，所以抵消了。唯一有用的 \(|F|\) 就是内部不含其他连通块的，也就是小正方形，这也是好算的。
NTT 需要用一个大模数或者双模数 CRT 合并。
考虑 \(|F|\) 的时候没把权值拿进来手模几个，感觉和正解擦肩而过了。