海草。海草。
Semi-local string comparison: Algorithmic techniques and applications 的导读。
蒙日阵
现在有一个矩阵$M$，它的下标是整数。定义它的分布矩阵$M^\Sigma$是它的子区间和，它的密度矩阵$M^\square$是它的二维差分，这里分布矩阵的下标是整数$+\frac{1}{2}$，密度矩阵的下标是整数。
一个矩阵是简单的，当且仅当它的$\square$的$\Sigma$是它，也就是说它没有什么常数项之类的东西。
一个矩阵是蒙日的，当且仅当它的$\square$非负。
一个矩阵是简单单位蒙日的，当且仅当它是一个排列矩阵的$\Sigma$，以下我们省略简单。一个矩阵是亚单位蒙日的，当且仅当它是一个亚排列矩阵(每行每列不超过一个$1$，其它位置都是$0$)的$\Sigma$。
以下默认矩乘是(min,+)矩乘。
几个简单结论是，蒙日阵，亚单位蒙日阵，单位蒙日阵，对乘法都是封闭的。蒙日阵的和还是蒙日阵，因为$\square$是线性变换，但单位蒙日阵显然不满足这个。
蒙日阵乘法可以二维决策单调性做到$O(n^2)$。乘向量可以smawk做到$O(n)$。用$\square$表示的亚单位蒙日阵乘法可以做到$O(n\log n)$，乘向量可以$O(n)$。
semi-local lcs
我们都知道lcs是一个网格状dag上的最长路，也就是说$(i,j)\stackrel{0}{\rightarrow}(i+1,j),(i,j+1)$，如果$a_i=b_j$则还有一条$(i,j)\stackrel{1}{\rightarrow}(i+1,j+1)$。
现在我们要求边界上任意两个点之间的最长路。可以在左边和右边加满边转化成上边任意一个点到下边任意一个点的最长路。这里可以看看那个概要里的图。
答案$A$必然是蒙日的。考虑我们在上边选择$i,i+1$，下边选择$j,j+1$，要证明$a_{i,j+1}+a_{i+1,j}\leq a_{i,j}+a_{i+1,j+1}$，那么我们找到$i$到$j+1$的路径，$i+1$到$j$的路径，它们必然相交于至少一点，随便取一点，把前后交换，就得到$i$到$j$，$i+1$到$j+1$的一个方案，非常对对吧。但是这里只有$i<j$的情况，如果$i>j$，我们定义$a_{i,j}=j-i$，可以发现这让它是蒙日的。
不过蒙日的定义是$\geq$，不过关系不大，把所有数取反就好了。
更进一步的，$b_{i,j}=j-i-a_{i,j}$是单位蒙日的。显然它的$\square$是整数。考虑左边和下边，有$b_{n,j}=0,b_{i,0}=0$，所以它是简单的。继续考虑右边和上边，以右边为例，有$b_{i,n+m}-b_{i+1,n+m}=1-a_{i,n+m}+a_{i+1,n+m}$，那么根据定义有$a_{i,n+m}=a_{i+1,n+m}=m$，上边类似。所以其$\square$的行之和和列之和都是$1$，所以它必然是一个排列，所以$A$是单位蒙日的。看起来补的这部分把它从亚单位蒙日变成了单位蒙日。
试看看! 例题1.7
ur25 C. 装配序列
一个排列循环无穷次，多次查询前缀(严格)lis长度。
显然lis长度不超过$n$，并且循环$n$次则必然到达$n$，那么我们只需要对于每个长度求出最短的前缀即可。