[Dr.Lib]Note:Algorithm – 莫队算法

莫队算法:对于两个区间的查询[l1,r1] ,[l2,r2]如果每增加一个区间元素或者删除,都能做到O(1)的话
那么从[l1,r1]转移到[l2,r2],暴力可以做到|l1-l2|+|r1-r2|,就是manhattan距离
莫队的论文一直没有找到,所以只是大致的了解下,应该是证明出构造出哈密尔顿路径是最优的。
但是可以用manhattan mst来构造,大约会是两倍,然后莫队证明出这样转移的上限是O(n*sqrt(n))。
所以对于这种无修改的区间查询来说
可以先将所有的区间,看成二维平面上的点,求一次manhattan mst,然后根据mst来进行转移
相邻的两个区间的查询转移,暴力解决。

Via http://blog.csdn.net/huzecong/article/details/8576908

http://blog.csdn.net/acm_cxlove/article/details/8894431

在此感谢

据说这个算法是莫涛提出的(Orz!),但是在网上到处都搜不到相关资料,最后问pty才知道的。这个算法是用于处理一类不带修改的区间查询问题的离线算法,其核心在于利用曼哈顿距离最小生成树算法对区间处理顺序进行处理。比如下面这个例题(清橙A1206《小Z的袜子》,就是莫队出的题):

给定一个长为N的序列,每个元素的值是其颜色。有M次询问,每次询问从一个区间中随机选取两个元素同色的概率。

一次询问[l,r]的答案即,其中是区间中第i中颜色的个数。显然暴力是O(NM)的,而且一般的区间问题的思路似乎不适用。

我们先考虑一个简化的问题:所有的查询区间的左端点都是1。那么我们可以按右端点排序,假设已经处理出了[1,r]的答案,考虑转移到[1,r+k],即添加k个元素,这个可以在O(k)的复杂度内求出。那么处理所有区间的复杂度(不考虑排序)就是O(N)。

那么如果是从[l,r]转移到[l’,r’]呢?复杂度即O(|r’-r|+|l’-l|),也即点(l,r)到点(l’,r’)的曼哈顿距离。那么如果将所有询问转化成二维平面中的点,求曼哈顿距离最小生成树,再按照生成树的顺序做,就可以最小化区间之间转移的复杂度。可以证明(我不会证……似乎莫队的论文里有),这样做的复杂度是O(N1.5)的。问题也就得到了解决。

[Dr.Lib]Note:Math – \(\Sigma \frac{1}{n^{2}}\)

转载自http://www.ivy-end.com/archives/1098


今天我们来介绍一个曾经在数列题中做过无数遍的数列\(a_{n}=\frac{1}{n^{2}}\),为了方便下文的讨论,我们记\(S_{n}\)为数列\(a_{n}\)的前\(n\)项和。我们做过最熟悉的题目莫过于证明\(S_{n}<2\),这个证明对于大家来说应该是非常容易的\[S_{n}=\sum_{i=1}^{n}\frac{1}{i^{2}}=1+\sum_{i=2}^{n}\frac{1}{i\cdot\left(i-1 \right )}=2-\frac{1}{n}.\]

那么大家是否考虑过,\(\lim_{n \to \infty }S_{n}\)究竟等于多少?我记得严桂华讲过欧拉曾经计算过这个问题,今天在国外一个数学讨论网站上翻到了一篇关于如何计算\(\lim_{n \to \infty }S_{n}\)的问答(原文地址)。在此仅介绍几种方法。

首先给出结果,再用多种方法进行证明\[\lim_{n \to \infty }S_{n}=\frac{\pi^{2}}{6}.\]不得不说,这一结果是非常不可思议的,因为它居然包含了\(\pi\)。读者如果不相信的话,可以自行计算一下,当\(n\)趋向于正无穷时,答案便越接近\(\frac{\pi^{2}}{6}\)。

好了,废话不说,我们进入证明部分。

法一:

当\(0<x<\frac{\pi}{2}\)时,有\(0<\sin{x}<x<\tan{x}\)。至于这个命题的证明,请参考下图:

Mathematics 003-1-1

这样,我们可以得到\[\frac{1}{\tan^{2}{x}}<\frac{1}{x^{2}}<\frac{1}{\sin^{2}{x}}.\]我们知道,\(\frac{1}{\tan^{2}{x}}=\frac{1}{\sin^{2}{x}}-1\)(很容易由三角恒等式导出)。将区间\(\left(0,\frac{\pi}{2}\right)\)等分成\(2^{n}\)个部分,令\(x_{k}=\frac{\pi}{2}\cdot\frac{k}{2^{n}}\),并将不等式两边对\(x_{k}\)进行求和,可以得到\[\sum_{k=1}^{2^n-1} \frac{1}{\sin^2 x_k} – \sum_{k=1}^{2^n-1} 1 < \sum_{k=1}^{2^n-1} \frac{1}{x_k^2} < \sum_{k=1}^{2^n-1} \frac{1}{\sin^2 x_k}.\]我们不妨将不等式右边的表达式记为\(T_{n}\),那么原不等式可以化简为\[T_{n} – \left(2^n – 1\right) < \sum_{k=1}^{2^n-1} \left( \frac{2 \cdot 2^n}{\pi} \right)^2 \frac{1}{k^2} < T_n.\]接下来我们主要考察\(T_{n}\)。它看起来是一个非常复杂的求和,实际上可以非常简单的计算出来。首先,我们考虑下面的式子\[\frac{1}{\sin^2 x} + \frac{1}{\sin^2 (\frac{\pi}{2}-x)} = \frac{\cos^2 x + \sin^2 x}{\cos^2 x \cdot \sin^2 x} = \frac{4}{\sin^2 2x}.\]因此,如果我们将\(T_{n}\)以\(\frac{\pi}{4}\)为中点进行配对(选取区间\(\left(0,\frac{\pi}{2}\right)\)左边的点\(x_{k}\),与右边的点\(\frac{\pi}{2}-x_{k}\)),考虑递推,再加上中点\(\frac{1}{\sin^{2}{\frac{\pi}{4}}}=2\),则可以得到\[T_{n}=4T_{n-1}+2.\]又\(T_{1}=2\),我们可以很容易的得到\(T_{n}\)的通项公式\[T_n = \frac{2(4^n-1)}{3}.\]于是,我们得到了这样的不等式\[\frac{2(4^n-1)}{3} – (2^n-1) \leq \frac{4^{n+1}}{\pi^2} \sum_{k=1}^{2^n-1} \frac{1}{k^2} \leq \frac{2(4^n-1)}{3}.\]两边同时乘以\(\frac{\pi^{2}}{4^{n+1}}\)使得不等式的中间与我们的目标形式更加相似,这样我们又得到一个不等式\[\frac{\pi^{2}}{4^{n+1}} \cdot \frac{2(4^n-1)}{3} – (2^n-1) \leq \sum_{k=1}^{2^n-1} \frac{1}{k^2} \leq\frac{\pi^{2}}{4^{n+1}} \cdot \frac{2(4^n-1)}{3}.\]当\(n\rightarrow\infty\)时,不等式左右两边同时趋向于\(\frac{\pi^{2}}{6}\),由夹逼准则得\(\lim_{n \to \infty }S_{n}=\frac{\pi^{2}}{6}\)。证毕。

法二:

我们可以借助函数\(f\left(x\right)=x^{2},x\in\left[-\pi,\pi\right]\)来找到它对应的三角傅立叶级数\[\frac{a_{0}}{2}+\sum_{n=1}^{\infty }(a_{n}\cos nx+b_{n}\sin x),\]且它是周期收敛的。

又\(f\left(x\right)\)为偶函数,这足够让我们得到它的系数\[a_{n}=\frac{1}{\pi }\int_{-\pi }^{\pi }f(x)\cos nx\;dx\qquad n=0,1,2,3,\cdots,\]因为\[b_{n}=\frac{1}{\pi }\int_{-\pi }^{\pi }f(x)\sin nx\;dx=0\qquad n=1,2,3,\cdots.\]令\(n=0\)得\[a_{0}=\frac{1}{\pi }\int_{-\pi }^{\pi }x^{2}dx=\frac{2}{\pi }\int_{0}^{\pi}x^{2}dx=\frac{2\pi ^{2}}{3}.\]当\(n=1,2,3,\cdots\)时,我们有\[a_{n}=\frac{1}{\pi }\int_{-\pi }^{\pi }x^{2}\cos nx\;dx\\=\frac{2}{\pi }\int_{0}^{\pi }x^{2}\cos nx\;dx=\frac{2}{\pi }\times \frac{2\pi }{n^{2}}(-1)^{n}=(-1)^{n}\frac{4}{n^{2}},\]因为\[\int x^2\cos nx\;dx=\frac{2x}{n^{2}}\cos nx+\left( \frac{x^{2}}{n}-\frac{2}{n^{3}}\right) \sin nx.\]因此\[f(x)=\frac{\pi ^{2}}{3}+\sum_{n=1}^{\infty }\left( (-1)^{n}\frac{4}{n^{2}}\cos nx\right).\]又\(f\left(\pi\right)=\pi^{2}\),我们可以得到\[\pi ^{2}=\frac{\pi ^{2}}{3}+\sum_{n=1}^{\infty }\left( (-1)^{n}\frac{4}{n^{2}}\cos \left( n\pi \right) \right)\]即\[\pi ^{2}=\frac{\pi ^{2}}{3}+4\sum_{n=1}^{\infty }\left( (-1)^{n}(-1)^{n}\frac{1}{n^{2}}\right)\]进一步化简得\[\pi ^{2}=\frac{\pi ^{2}}{3}+4\sum_{n=1}^{\infty }\frac{1}{n^{2}}.\]因此\[\sum_{n=1}^{\infty }\frac{1}{n^{2}}=\frac{\pi ^{2}}{4}-\frac{\pi ^{2}}{12}=\frac{\pi ^{2}}{6}.\]证毕。

法三:

当\(x=0\)时\(\sin{x}\)可以使用泰勒级数展开\[\sin x = x – \frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\cdots.\]于是我们可以得到\[\frac{x^3}{3!}=x\left(\frac{x^2}{\pi^2} + \frac{x^2}{2^2\pi^2}+ \frac{x^2}{3^2\pi^2}+\cdots\right)=x^3\sum_{n=1}^{\infty}\frac{1}{n^2\pi^2},\]即\[\sum_{n=1}^\infty\frac{1}{n^2}=\frac{\pi^2}{6}.\]证毕。

法四:

设\(z\)为复数,考虑\[\frac{\pi^2}{\sin^2\pi z}=\sum_{n=-\infty}^{\infty}\frac{1}{(z-n)^2}\]由复变函数分析可得\[\frac{\pi^2}{\sin^2\pi z}-\frac{1}{z^2}=\sum_{n=1}^{\infty}\frac{1}{(z-n)^2}+\sum_{n=1}^{\infty}\frac{1}{(z+n)^2}.\]这样,当右边\(z=0\)时,我们就可以得到\[\lim_{z\to 0}\left(\frac{\pi^2}{\sin^2\pi z}-\frac{1}{z^2}\right)=2\sum_{n=1}^{\infty}\frac{1}{n^2}.\]又\[\lim_{z\to 0}\left(\frac{\pi^2}{\sin^2\pi z}-\frac{1}{z^2}\right)=\frac{\pi^2}{3}.\]因此\[\sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{\pi^2}{6}.\]证毕。

法五:

这是欧拉的方法。令\[s=\sin^{-1}{x}.\]那么\[\int_{0}^{\frac{\pi}{2}}sds=\frac{\pi^{2}}{8}.\]但是\[\int\limits_0^1 {\frac{{{{\sin }^{ – 1}}x}}{{\sqrt {1 – {x^2}} }}dx} = \frac{{{\pi ^2}}}{8}.\]又\[{\sin ^{ – 1}}x = \int {\frac{{dx}}{{\sqrt {1 – {x^2}} }}} = x + \frac{1}{2}\frac{{{x^3}}}{3} + \frac{{1 \cdot 3}}{{2 \cdot 4}}\frac{{{x^5}}}{5} + \frac{{1 \cdot 3 \cdot 5}}{{2 \cdot 4 \cdot 6}}\frac{{{x^7}}}{7} + \cdots.\]我们可以得到\[\int\limits_0^1 {\left\{ {\frac{{dx}}{{\sqrt {1 – {x^2}} }}\int {\frac{{dx}}{{\sqrt {1 – {x^2}} }}} } \right\}} = \int\limits_0^1 {\left\{ {x + \frac{1}{2}\frac{{{x^3}}}{3}\frac{{dx}}{{\sqrt {1 – {x^2}} }} + \frac{{1 \cdot 3}}{{2 \cdot 4}}\frac{{{x^5}}}{5}\frac{{dx}}{{\sqrt {1 – {x^2}} }} + \cdots } \right\}}.\]但是\[\int\limits_0^1 {\frac{{{x^{2n + 1}}}}{{\sqrt {1 – {x^2}} }}dx} = \frac{{2n}}{{2n + 1}}\int\limits_0^1 {\frac{{{x^{2n – 1}}}}{{\sqrt {1 – {x^2}} }}dx}.\]这样,可以得到\[\int\limits_0^1 {\frac{{{x^{2n + 1}}}}{{\sqrt {1 – {x^2}} }}dx} = \frac{{\left( {2n} \right)!!}}{{\left( {2n + 1} \right)!!}}.\]又所有的次数都是奇数,所以最终的结果为\[\frac{{{\pi ^2}}}{8} = 1 + \frac{1}{2}\frac{1}{3}\left( {\frac{2}{3}} \right) + \frac{{1 \cdot 3}}{{2 \cdot 4}}\frac{1}{5}\left( {\frac{{2 \cdot 4}}{{3 \cdot 5}}} \right) + \frac{{1 \cdot 3 \cdot 5}}{{2 \cdot 4 \cdot 6}}\frac{1}{7}\left( {\frac{{2 \cdot 4 \cdot 6}}{{3 \cdot 5 \cdot 7}}} \right) \cdots,\]\[\frac{{{\pi ^2}}}{8} = 1 + \frac{1}{{{3^2}}} + \frac{1}{{{5^2}}} + \frac{1}{{{7^2}}} + \cdots.\]令\[1 + \frac{1}{{{2^2}}} + \frac{1}{{{3^2}}} + \frac{1}{{{4^2}}} + \cdots = \omega.\]则\[\frac{1}{{{2^2}}} + \frac{1}{{{4^2}}} + \frac{1}{{{6^2}}} + \frac{1}{{{8^2}}} + \cdots = \frac{\omega }{4}.\]这样,我们可以得到\[\frac{\omega }{4} + \frac{{{\pi ^2}}}{8} = \omega.\]即\[\omega = \frac{{{\pi ^2}}}{6}.\]证毕。

法六:

\[\sum_{i=1}^{n}\frac{1}{i^{2}}=\zeta(2)=\frac{4}{3}\sum_{n=0}^{+\infty}\frac{1}{(2n+1)^2}=\frac{4}{3}\int_{0}^{1}\frac{\log y}{y^2-1}dy\]\[=\frac{2}{3}\int_{0}^{1}\frac{1}{y^2-1}\left[\log\left(\frac{1+x^2 y^2}{1+x^2}\right)\right]_{x=0}^{+\infty}dy=\frac{4}{3}\int_{0}^{1}\int_{0}^{+\infty}\frac{x}{(1+x^2)(1+x^2 y^2)}dx\,dy\]
\[=\frac{4}{3}\int_{0}^{1}\int_{0}^{+\infty}\frac{dx\, dz}{(1+x^2)(1+z^2)}=\frac{4}{3}\cdot\frac{\pi}{4}\cdot\frac{\pi}{2}=\frac{\pi^2}{6}.\]证毕。

就介绍这几种方法吧,大家可以有选择的进行阅读。以后数学作业中再有证明\(S_{n} < 2\)的时候,不妨这样写\(\lim_{n \to \infty }S_{n}=\frac{\pi}{6} < 2\),怕老师不承认,可以顺便证明一下,至于给不给分,就不好说了。

 

[Dr.Lib]Note:Math – Extend Baby Step Giant Step

这种数学题都是转AC大神的……以及Seter

http://hi.baidu.com/aekdycoin/item/236937318413c680c2cf29d4

http://seter.is-programmer.com/posts/32188.html

Baby Step Giant Step

\[A^{x}=B (\mod C) 0\leq x <C,C\in \mathbb{P}\]

求解x,我们可以做一个等价

\[x = i\ast m + j  ( 0 \leq i,j< m) ,m = \lceil \sqrt{C} \rceil\]

而这么分解的目的无非是为了转化为:

\[(A^{i})^{m} * A^{j} = B \mod C\]

之后做少许暴力的工作就可以解决问题:
(1) for i = 0 -> m, 插入\( Hash (A^i \mod C, i) \)

(2) 枚举 i ,对于每一个枚举到的i,令  \( {A}' = (A^m)^i \mod C\)
我们有\[A' * A^j = B \mod C\]

显然\(A'B,C\),均已知,而由于C为素数,那么(AA,C)无条件为1

令\(p=(A^M)^i \mod C,x=A^j \mod C\)则\(p*x=B\mod C\)。

我们从0开始枚举i直到i*M超过C-1,则相当于知道了p,要求x。

由于 (A',C)=1 ,于是对于这个模方程解的个数唯一(可以利用扩展欧几里得或 欧拉定理来求解)

那么对于得到的唯一解x,在Hash表中寻找(x,j),如果找到,则返回  \(i*m+j>0\) 。

如果需要得到 x > 0的解,那么只需要在上面的步骤中判断 当 \(i*m+j>0\) 的时候才返回。

扩展Baby Step Giant Step

\[A^{x}=B (\mod C) 0\leq x <C,C\in \mathbb{N^*}\]

当C不是素数的时候能否直接套用呢?当然不可以……最直接的问题就是,不一定存在逆元!

考虑一个\(G'\)同时是ABC的因数,令\(B'=\frac{B}{G'},C'=\frac{C}{G'}\),则当x不等于0时,

\(\frac{A}{G'}*A^(x-1)=B'\mod  C'\)。

这样多弄几次,C的因数就越来越少,直到(A,C)=1。

那么如何选取\(G'\)呢?AC大神告诉你:不断取\(G'=gcd(A,C')\),直到\(G'\)=1。如果任意一个\(G'\)不是\(B'\)的因数则一定无解。

假设取了r次\(G'\),然后所有\(G'\)的积是G,则问题变为\(\frac{A^r}{G}*A^{x-r}=B'\mod C'\),令\(D=\frac{A^r}{G}\)(一定是整数),则由于此时\((A,C')=1\),所以\((D,C')=1\)。

那么上面算法中只要变成求\(D\)对于\(C'\)的逆元就可以了,返回的答案还要加上r。

还有一点小问题,就是这样得出的答案是大于等于r的。但是即使每次\(G'=2\),r最大也只有\(log_{2}C\),那么这些再暴力求解就可以了。

[Dr.Lib]Note:Data Structures – 左偏树

左偏树真是个超好写的东西!支持合并,插入,删除最小值三个操作。后两个操作都可以看成第一个操作的拓展,如删除最小值是合并根的两棵子树,插入则直接将元素看作一个左偏树——所以只要写个Merge就可以了!

左偏树保证左子树深度大于等于右子树深度,同时符合堆性质。合并LT1,LT2(假设LT1中最小值比LT2小,否则交换)时,递归合并LT1的右子树和LT2替换掉LT1,然后如果LT1不符合左偏性质,则交换LT1的子树。

小小的提示:构树时,逐个插入是O(nlgn)的。这里可以有O(n)的复杂度的算法:先把所有元素构成n个单元素左偏树放进队列,然后每次取出两个合并后放入队列尾,直到只剩下一棵左偏树。

——http://seter.is-programmer.com/posts/30733.html

 

[Dr.Lib]Note:Algorithm – Manhattan minimum spanning tree

Via http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep

We first break this down into a simpler problem. Standard MST algorithms for general graphs (e.g., Prim's algorithm) can compute the MST in O((E + N) log N) time for E edges. If we can exploit geometric properties to reduce the number of edges to O(N), then this is merely O(N log N). In fact we can consider, for each point P, only its nearest neighbors in each of the 8 octants of the plane (see the figure below). The figure shows the situation in just one of the octants, the West-Northwest one. Q is the closest neighbour (with the dashed line indicating points at the same Manhattan distance as Q), and R is some other point in the octant. If PR is an edge in a spanning tree, then it can be removed and replaced by either PQ or QR to produce a better spanning tree, because the shape of the octant guarantees that |QR| ≤ |PR|. Thus, we do not need to consider PR when building the spanning tree.

Octants

This reduces the problem to that of finding the nearest neighbour in each octant. We'll just consider the octant shown; the others are no different and can be handled by symmetry. It should be clear that within this octant, finding the nearest neighbour is equivalent to just finding the point with the largest value of x − y, subject to an upper bound on x + y and a lower bound on y, and this is the form in which we'll consider the problem.

Now imagine for the moment that the lower bound on y did not exist. In this case we could solve the problem for every P quite easily: sweep through the points in increasing order of x + y, and Q will be the point with the largest x − y value of those seen so far. This is where the divide-and-conquer principle comes into play: we partition the point set into two halves with a horizontal line, and recursively solve the problem for each half. For points P in the upper half, nothing further needs to be done, because points in the bottom half cannot play Q to their P. For the bottom half, we have to consider that by ignoring the upper half so far we may have missed some closer points. However, we can take these points into account in a similar manner as before: walk through all the points in x + y order, keeping track of the best point in the top half (largest x − y value), and for each point in the bottom half, checking whether this best top-half point is better than the current neighbour.

So far I have blithely assumed that any set of points can be efficiently partitioned on Y and also walked in x + y order without saying how this should be done. In fact, one of the most beautiful aspects of this class of divide-and-conquer plus line-sweep algorithms is that it has essentially the same structure as a merge sort, to the point that a merge-sort by x + y can be folded into the algorithm in such a way that each subset is sorted on x + y just when this is needed (the points initially all being sorted on Y). This gives the algorithm a running time of O(N log N).

The idea of finding the closest point within an angle range can also be used to solve the Euclidean MST problem, but the O(N log N) running time is no longer guaranteed in the worst cases, because the distance is no longer a linear equation. It is actually possible to compute the Euclidean MST in O(N log N) time, because it is a subset of the Delaunay triangulation.