\[[header] \renewcommand{\rar}{\rightarrow} \renewcommand{\les}{\leqslant} \renewcommand{\ges}{\geqslant} \renewcommand{\dsp}{\displaystyle} \renewcommand{\mb}{\mathbb} \renewcommand{\bs}{\backslash} \renewcommand{\ep}{\varepsilon} \renewcommand{\eqs}{\Leftrightarrow} \renewcommand{\ex}{\exist} \renewcommand{\dt}{\delta} \renewcommand{\al}{\alpha} \renewcommand{\be}{\beta} \renewcommand{\ga}{\gamma} \renewcommand{\bal}{\begin{align*} } \renewcommand{\eal}{\end{align*} } \renewcommand{\Dt}{\Delta} \renewcommand{\d}{\mathrm{d} } \renewcommand{\sg}{\sigma} \renewcommand{\th}{\theta} \renewcommand{\|}{ {\bigg{|}} } \renewcommand{\lam}{\lambda} \renewcommand{\pa}{\partial} \newcommand\pw[2]{\frac{\pa #1}{\pa #2}} \renewcommand{\bd}{\bold} \renewcommand{\nb}{\nabla} \renewcommand{\mrm}{\mathrm} \renewcommand{\Ga}{\Gamma} \renewcommand{\wg}{\wedge} \renewcommand{\mscr}{\mathscr} \renewcommand{\aecvg}{\stackrel{a.e.}{\longrightarrow}} \renewcommand{\aucvg}{\stackrel{a.u.}{\longrightarrow}} \renewcommand{\mucvg}{\stackrel{\mu}{\longrightarrow}} \renewcommand{\deq}{\xlongequal{\ \ _{_d}\ \ }} \newcommand\cvg[1]{\stackrel{#1}{\longrightarrow}} \newcommand\ffm[3]{#1 \d y\wg\d z+#2\d z\wg \d x+#3\d x\wg \d y} \renewcommand{\dv}{\nabla\cdot} \renewcommand{\cl}{\nabla\times} \renewcommand{\vp}{\varphi} \renewcommand{\fa}{\forall} \renewcommand{\tx}{\text} \newcommand{\(}{\left(} \newcommand{\)}{\right)} \newcommand{\Mn}{\mathfrak M} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \newcommand{\og}{\omega} \newcommand{\[}{\left[} \newcommand{\]}{\right]} \newcommand{\sea}{\searrow} \newcommand{\nea}{\nearrow} \renewcommand\thm[2]{ \colorbox{rgb(255,127,127)} {$ \colorbox{rgb(80,150,255)}{#1}\\ \begin{align*}#2\end{align*} $} } \newcommand{\mcal}{\mathcal}\]
虽然海草有了, 蒙日乘也有了, 但是还没有结果用海草去解释蒙日乘的, 所以现在蒙日乘算法的理论相对于选手较为复杂, 不容易写出
对于tcs角度, 使用蒙日乘看上去有望得到LCS相关问题更内在的结果, 可是对于一个只有理论而没有intuition的工具也不便使用
在本学期探索算法设计的project时, 笔者找到了海草解释的对应, 完全排除了理论的推导, 只剩海草没有细节的几何意义(没有形式上的半下标和边界条件)
因为结果十分简单, 所以本文十分简单, 目标是考场上可以10min写出蒙日乘
前置可见海草基础(待更), 学会之后自然是得心应手
下面是本文草稿(图片待补)
假设我们现在需要乘两个海草\(p,q\), 下标为\([n]\)
我们可以把\(p,q\)各分解为一堆海草的乘积
第一步自然是对应于蒙日乘的二分, 我们取一\(mid\)
将\(p\)中海草按终点在\([1,mid],[mid+1,n]\)分为两部分, 将起点各自保持相对顺序分离在左右, 这样我们得到从\([1,mid]\)到\([1,mid]\)的海草\(p_1\), 以及\([mid+1,n]\)上的海草\(p_2\)
同理将\(q\)按起点所在区间分为\(q_1,q_2\)
我们发现\(p=A\circ (p1,p2)\),其中\((p_1,p_2)\)表示海草按下标拼接, \(A\)是一个移位海草, 向前复合表示将\((p_1,p_2)\)的海草起始点冒泡至\(p\)的顺序
同理\(q=(q_1,q_2)\circ B\), \(B\)表示将终点移位的海草
那么\(p\circ q=A\circ(p_1\circ q_1,p_2\circ q_2)\circ B\), \(C=(p_1\circ q_1,p_2\circ q_2)\)递归下去算
那么考虑计算这个\(A\circ C\circ B\)
\(A\circ C\)是容易的, 因为\(C\)此时终点相当有序, \(A\circ C\)就相当于把\(C\)的起点冒泡至\(p\)的顺序
但是这个时候在末尾复合\(B\)就不一样了, 考虑\(B\)由哪些邻交换构成, 我们发现这是试图将 在\([mid+1,n]\)结尾 的海草挪到左边去
记录\(A\circ C\)终点到\(1,...,n\)对应的起点\(a_1,a_2,...,a_n\), 这操作相当于是在把\(a_{mid+1}\)向左移到原位(\(q\)中的原位), 接着\(a_{mid+2},...\)
交换的过程是冒泡排序, 遇到比当前手上拿的更大的就交换
$ $ 此处应有伪代码
而且目标停止位置是单增的
我们将其考虑为一个数据结构问题, 我们预留出\(mid+1,...,n\)欲插入的目标位置, 视作白点, 将\(1,...,mid\)所在位置视为黑点
先看黑点\(i\), 这里\(1\le i\le mid\)对应插入空白之前的\(a_i\), 我们知道\([mid+1,n]\)有一段前缀在交换的时候会经过这个黑点
假如有\(k\)个\([mid+1,mid+k]\)中的点经过这里, 那这个黑点最终的值就是\(a_i\)与右边所有的\(a_{i+1},...,a_{mid+k}\)中第\(k\)大值求一个\(\min\)
再看白点, 假设其右第一个黑点是\(a_i\)(没有就是\(a_{mid+1}\)), 假设最终留在这个位置的白点是右边第\(k\)个\(a_{mid+k}\)
考虑\(a_{i},...,a_{i+k-1}\)中的前\(k-1\)已经被取走, 那么此时从\(a_{mid+k}\)开始向左取, 不断求最大
那么我们会发现如果\(a_i,...,a_{mid+k}\)中第\(k\)大没有\(a_{mid+k}\)大, 那最终值就是初始时手持的\(a_{mid+k}\), 而如果比其大, 那么就是第\(k\)大, 最终是比较了一个\(\max\)
如何维护这个set里的第\(k\)大呢, 我们发现这涉及到 在集合中加入一个数并将\(k\)加\(1\), 或者删除一个数, 而第\(k\)大总是单增的, 可以\(O(n)\)维护
加上分治一共\(O(n\log n)\), 可以发现没有边界条件和细节
最终实现以上算法只需要定义一些排列的操作(如求逆, 复合, 拆分), 将排列像操作torch张量一样即可
目前未决的问题是, 循环海草如何设计如上海草乘, 这也是笔者算法设计课程project的最终目标
标签：...,速通,renewcommand,蒙日,mid,海草,newcommand,单位,circ From： https://www.cnblogs.com/C127/p/18528780