Felix021

2年多以前看的算法，当时基本看懂了（实际上还是有问题的），今天再翻出来，感觉基本忘了，重新实现一遍，试着自己把推导过程也写写。非常赞的算法。

RMQ: Range Minimum Query, 区间最小值查询。已知数组在区间 [0, n) 有定义，给出 i, j (0 <= i < j <=n)，求 [i, j) 之间的最小值。

朴素算法非常简单，但是显然，每次查询是O(N)的，效率很低：
由于经常遇到需要多次查询的情况，所以朴素算法不合意。一个比较好的改进是使用线段树/树状数组，首先通过O(NlogN)预处理，让每个分支节点保存了其所有叶子节点的最小值（由底向上递推)。这样每次查询的时候，就可以在O(logN)的时间内得到结果。具体代码稍繁琐，这里不写了。

最好的方法，是用叫做sparse_table的算法，其思路和线段树很像，区别是通过O(NlogN)的预处理，可以让查询的时间复杂度降低到O(1)。其具体思路为：

预处理：
1. 记F[s][p] = min{ arr[i] | s <= i < s + 2^p} = min(arr[s..(s + 2^p - 1)])。例如， F[1][2] = min{ arr[i] | 1<= i < 5} = min(arr[1..4])。
2. 由1，易推知，F[s][0] = min { arr[i] | s <= i < s + 1} = arr[s].
3. 通过由底向上递推的预处理得到所有满足（s + 2^p <= n, 即区间[s, s + 2^p) 包含于[0..n)区间内）的F[s][p] = min(F[s][p-1], F[s+2^(p-1)][p-1])。例如， F[2][3] = min(arr[2..9]) = min(min(arr[2..5]), min(arr[6..9])) = min(F[2][2], F[6][2]) = min(F[2][3-1], F[2 + 2^(3-1)][3-1])。

查询[i, j)：
1. 令 k = log2(j - i)取整，则 (j - 2^k) <= (i + 2^k)，即区间 [i, i + 2^k) 和 [j - 2^k, j) 必定覆盖 [i, j)。例如，区间[3, 8)，k = log2(8-3)取整 = 2，则 [3, 7), [4, 8) 覆盖 [3, 8)。
2. RMQ[i, j) = min(F[i][k], F[j - 2^k][k]).

----扩展---
LCA（树中任意两个节点的最近公共祖先）问题，是可以通过RMQ+DFS来完成的，详见LCA问题。ZOJ 1141是一道纯LCA问题。

具体实现和检验代码如下（做了一点改进，F[s][p]中存放的是[s, s + 2^p)中最小值在数组中的索引）：

C标准中的qsort函数，可以对任意类型的数组进行快速排序，用起来也还算方便，不过行为有一点诡异。加上之前曾经看过一篇文章（沈大写的，曾经登上过ecom的双周刊，居然在这个youalab.com也等出来了-。-），说是qsort不是线程安全的，所以把glibc的代码翻出来，看看qsort的具体实现。

用Ubuntu的话，找代码就很容易了：
可以看到qsort是在stdlib.h里面的，源码在msort.c 302行，调用了qsort_r函数：其中__compar_fn_t就是 int (*)(const void *, const void *)类型的函数指针，__compar_d_fn_t则是 int (*)(const void *, const void *, void *)类型的函数指针(为什么还有个void *呢?很神奇~求解)。

qsort_r函数也在msort.c中，约164行起。为了榨干CPU的性能，写了很多代码来优化效率，其流程大致是：

1. 判断额外所需内存大小，如果很小(<1024B)，在栈上分配；否则获取系统内存参数——如果比可用内存小，试图在堆上分配；如果所需内存超过物理内存（为防出现不得不使用交换分区的情况致使性能恶化，故不分配），或者分配失败（可用空间不足），使用性能较差的stdlib/qsort.c中的_quicksort函数来排序。
    1.1. _quicksort位于 stdlib/qsort.c，对快排进行了两个改进：1. 将递归转化为递推; 2. 使用插入排序来处理4个元素以内的区间。不过用于交换两个元素的宏SWAP(a, b, size)没有额外的优化，比较意外（本来以为会考虑一次多个字节拷贝，或者使用duff device来减少循环）。

2. 分配成功的情况下，使用额外分配的空间，调用 msort_with_tmp() 函数来进行排序。
    2.1. 如果单个元素的大小超过32个字节，那么使用间接排序，分配空间时就有额外的判断，如果需要间接排序，则额外分配2n个指针的空间，前n个空间用于存放原指针，后n个空间用于按照所指元素大小存放排序好的指针。最后再按照排序好的指针顺序将元素拷贝。(注释中提到了Knuth vol. 3 (2nd ed.) exercise 5.2-10.，应该是指这个算法出自Knuth的《The Art of Computer Programming》卷3吧)
    2.2. 否则使用直接排序。这里也进行了一些优化，主要是为msort_with_tmp()提供p.var参数，完成针对元素的大小进行拷贝的优化：默认是使用gcc内置的__builtin_mempcpy来拷贝。
    2.3. msort_with_tmp对典型的快排也进行了非常赞的优化。
    2.3.1. 从msort_with_tmp的函数名和代码可以看出，这个算法不是就地排序，而是使用了第一步分配的O(N)的额外空间，这样可以让排序时的拷贝效率更高（这个优化应该对CPU的cache命中率也有较大的提高）。
    2.3.2. qsort_r传进来的参数p有个属性var
    (1) 默认情况下p.var = 4，使用mempcpy来进行拷贝。
    (2) 如果单个元素大于32bytes，p.var = 3, 表示是间接排序，拷贝的是指针，不是元素
    (3) 如果数组是按uint32_t对其的，且元素的大小是uint32_t的倍数，则可以进一步优化到每次按照uint32_t/uint64_t/unsigned long来进行拷贝，一次拷贝4或者8个字节，此时p.var = 0,1,2表示按照uint32_t, uint64_t, unsigned long拷贝。

直接在里头做了些注释，有兴趣的话可以更仔细地看看。可以的话自己去下了glibc的源码阅读，更有意思:D

上一篇谈到：“典型的情况是某些非法内存访问，Glibc会open("/dev/tty",...)，write()一些错误信息，然后open("/proc/self/maps", ...)把进程的内存映射表输出。还有一个更常见的情况，那就是用qsort。GCC的qsort实现，会主动open(/proc/meminfo)，获取一些信息，通过这些信息来最优化排序时的内存管理。” 通过执行可以看到进程执行的open系统调用。

对于这类情况，ptrace监控进程open系统调用，并获取文件名，检查文件名是否合法，如果合法，予以放行，这样就可以避免上述RE被误判为RF的情况了。

说起来很简单，但是具体做起来就有点麻烦。不过可以从我写woj-land的时候参考的ptrace教程《Playing with ptrace, 玩转ptrace》入手。这篇非常不错，强烈推荐有兴趣的同学学习学习：

Playing with ptrace, Part I — 玩转ptrace(一) http://www.kgdb.info/gdb/playing_with_ptrace_part_i/
Playing with ptrace, Part II — 玩转ptrace(二) http://www.kgdb.info/gdb/playing_with_ptrace_part_ii/

上篇以write系统调用为例，介绍了write系统调用的等价汇编码（当然是早期的了，现在的pc上linux貌似不用0x80了）、截获write系统调用，获取write系统调用的参数和返回值、甚至反转write系统调用的输出。具体的看原文了。

在这里，我需要peek的是read系统调用的参数。以x86为例，一个最简单的read系统调用：，大致等同于也就是说，可以通过获取x86 CPU寄存器的值来取得系统调用的参数，具体代码如下：
注意：虽然ebx中存放的是地址，但是不是用户程序可以直接读取的，需要通过ptrace的PTRACE_PEEKDATA命令来获取。该命令一次可以获取sizeof(long)个字节的内容，如果要获取字符串的所有内容，就得通过循环来完成。

此外，为了保证代码能够在x86_64架构下通过编译，需要把上述代码做个小修改：

通过这种方式，能够识别出open系统调用打开的文件，在保证系统安全的情况下，改善了Judge的识别能力。

更具体的代码可以参见：
http://code.google.com/p/woj-land/source/browse/trunk/code/judge/judge.h?spec=svn150&r=150#671

因为这两个东西占了地方，每次选盘符时总需要往下拉滚动条，很不爽。在网上搜到3篇文章，这里转载记录一下。

http://bbs.pcbeta.com/viewthread.php?tid=729301
http://bbs.pcbeta.com/viewthread.php?tid=729310
http://bbs.pcbeta.com/viewthread.php?tid=733262

“库” @  [HKEY_CLASSES_ROOT\CLSID\{031E4825-7B94-4dc3-B131-E946B44C8DD5}]
“家庭组” @  [HKEY_CLASSES_ROOT\CLSID\{B4FB3F98-C1EA-428d-A78A-D1F5659CBA93}]

修改注册表这里，需要右键->权限，给Administrators “完全控制” 的权限。

如果需要去掉这两项的显示，分别把键值 ShellFolder\Attributes 由原来的 b080010d 改为 b090010d，然后注销（其实Kill掉explorer也行）就行了。如果不想去掉显示，那么修改 SortOrderIndex 键值（默认是0x42、0x43），改到0x52或者更大，就会排到“计算机”后面了。

这个词组在ACM/ICPC的各大OJ出现频率还是很高的，意思是使用了“受限制的函数”。

而且几乎没有准确的文档可以定义什么是"Restricted Function"(RF，非彼“RF”)。因为开发者也很郁闷。一个大致可以接受的解释是，任何可能威胁到系统安全的代码都不应该被执行。更严格一点，任何解题所不需要用到的函数都不应该调用。但是这两个解释都不够准确。

作为一个需要编译并运行用户任意代码的系统，必然需要对用户的代码/程序进行额外的处理，过滤可能对服务器产生危险的操作。在woj-land ( http://code.google.com/p/woj-land ) 的实现中，是采用运行时监控程序的执行，通过ptrace来拦截并检查每一个系统调用，如果发现系统调用不在白名单中，即出现RF。具体的代码可参见：http://code.google.com/p/woj-land/source/browse/trunk/code/judge/rf_table.h

白名单机制是最安全的了，但是有缺陷。

首先是很难考虑到所有的情况。举例来说，你用C语言写的A+B来测试的话，需要的系统调用只有几个。大多数情况下能够满足要求，但是有时候却发现不对。比如说SYS_futex这个系统调用，如果不被允许，glibc写的程序在执行时可能会出问题。

其次是过于严格，导致部分常用且不影响系统安全的函数被限制死。比如说fflush，只需要用到SYS_lseek调用即可。

再次是有些异常情况。一个典型的情况是使用 qsort(arr, N, sizeof(arr), cmp); 这样的代码。实际上应当是sizeof(int)，不小心写错了，访问出错。典型的情况是某些非法内存访问，Glibc会open("/dev/tty",...)，write()一些错误信息，然后open("/proc/self/maps", ...)把进程的内存映射表输出。还有一个更常见的情况，那就是用qsort。GCC的qsort实现，会主动open(/proc/meminfo)，获取一些信息，通过这些信息来最优化排序时的内存管理。于是本来应该是运行时错误(段访问异常)，即Runtime Error(SIGSEGV)的情况也被误判为Restricted Function了。

終り.

闲谈 Restricted Function #2

首先在MATLAB的程序文件中找到如下文件:atlas_Athlon.dll(AMD系列的请用这个，其他的CPU也有相应的问题件)，这是对应处理器的数值运算优化文件,然后按如下步骤进行:

  1、右击我的电脑，选择属性，在"高级"选项卡中点击"环境变量" ，在系统变量下添加：
    变量名：BLAS_VERSION
    变量值：C:\Matlab7\bin\win32\atlas_Athlon.dll
    如果你安装在D盘，前面就改成D：\Matlab7\bin\win32\atlas_Athlon.dll

  2、右击MATLAB7.0的图标，属性，在兼容性 设置里面选择[√]以兼容模式运行这个程序，并选择 Vista Service Pack 2。

再次运行Matlab7 应该就OK了。

一切都是从，那道蚂蚁题，开始的
那题中的蚂蚁有20只，爬在长的木棒一根
左边蚂蚁10只向右爬
右边蚂蚁10只向左爬
蚂蚁爬的速度都相同
一碰头各自原速调头
然后就问，这些个蚂蚁，要碰多少次头才会从木棒上都掉下去

一说起这个问题，可能很多人有看过编程之美4.7 蚂蚁爬杆的问题：有一根27厘米长的细长木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置 处各有一只蚂蚁。木杆很细，不能同时通过2只蚂蚁。开始时候，蚂蚁的头朝左还是朝右是任意的，他们只会朝前走或者掉头，但是不会后退。当任意2只蚂蚁碰头后时，2只蚂蚁会同时掉转头朝反方向走。架设蚂蚁每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最短时间和最长时间。

留一些空间不剧透，有兴趣的同学可以先想想然后再往下看。

删除文件夹的时候，windows干的第一件事情貌似是计算所有的文件数量和大小，然后可以在删除过程中告诉你还要多久。有的时候小文件太多，这个过程相当漫长（比如用不了又卸不了的matlab安装文件夹）。这时候用命令提示符 rd /s /q DIRNAME 来删除就不那么罗嗦了。

更进一步，可以修改HK_CLASS_ROOT\Folder\Shell\，增加 一个 DELETE/command， cmd /c rd /s "%1"，就可以直接从右键这样删了。