Andre Lamothe在他的大作《3D游戏编程大师技巧》一书中提到，对游戏程序员来说，速度就是生命。因此使用优化技术来提高程序执行速度必不可少。其中SIMD编程占据很重要的位置。首先从MMX学起。以下转载自网上，留作学习之用。

MMX版本的Alpha Blend算法实现

这次我们的目标是: 超越普通的CPU玩家，用CPU的母语来优化程序!
MMX技术到现在来说可以算是基本大众化了，目前大多数个人电脑都应该能支持它。P55C， K6， PII， PIII…按照惯例，Intel公司将在以后的x86版本永远支持它。
(全文 …)

题目意思很简单，已知长方体表面上两个点，要求这两个点的最短表面距离。
一开始我是手推展开方式的，后来发现一共有12种展开情况，手写坐标变换相当麻烦。
然后改用递归方式展开。具体方式是先把第一个点转到底面(xOy平面)，然后对四个方向把底面翻开，把翻到的面作为新的底面。递归做下去，一直到第二个点也翻到底面上。
下面是我的代码：

题目意思是给出平面上n个不相邻的点，要求到这n个点的曼哈顿距离之和最小的点的个数ans2，和这个最小距离ans1。
点的坐标范围是-10000到10000（这个很重要）

考虑到曼哈顿距离的定义：|x – x0| + |y – y0|
这个定义是线性的，对称的
因此考虑分别在两个方向上解这个问题（曼哈顿距离的性质）

1. 对于x方向，定义x曼哈顿距离是|x – x0|，因为坐标范围很小，所以可以对所有可能的坐标，做一个线性扫描，求出fx，fx[x0]表示所有点到x0这个x坐标的x曼哈顿距离之和。对y方向相应地求出fy。
2. 有了fx和fy，我们可以用O(1)时间算出所有点到某一坐标(x0, y0)的曼哈顿距离之和ans1。现在选出fx[x0] + fy[y0]的最小值（剔除那些输入的点），这一步我是把fx和fy分别排序做的，复杂度O(nlogn)。应该能利用点的不相邻性质做得更好。
3. 现在统计满足题意的点的个数。利用fx计算数组nx，nx[i].coor表示此点的x坐标，nx[i].num表示x坐标是nx[i].coor的点的个数，nx[i].dist表示所有点到nx[i].coor的x曼哈顿距离之和。相应地计算ny。计算数组dd，dd[i]表示所有点到第i个点的曼哈顿距离之和。令t1 = sum(nx[i].num * ny[i].num), if (nx[i].dist + ny[i].dist == ans1)。令t2 = (dd[i] == ans1) 的个数。因此ans2 = t1 – t2。

下面是我的代码：

这个题目本质上要解决一个问题，给出一些区间[ai, bi)和一个数组，求数组中每个元素被区间覆盖的次数。

一开始想了个做法是线段树，后来想了个O(n)的做法。具体过程如下：

1. 去掉重复区间
2. f数组置0
3. 对每个区间[ai, bi)，令f[ai]++，f[bi]–
4. 设答案数组为c，则c[i] = sum(f[j]), 1 <= j <= i

关键是理解f数组的意义：f[i]表示第i个点对后续点的影响，而f[ai]++，f[bi]–保证了区间外的点不受影响，区间内的点都受+1的影响

以下是我的代码：

这个题目是Sherlock推荐我做的。
题目意思是给一个长度为n（n <= 100000）的序列，里面的数满足1 <= a[i] <= n。要找一个最长的连续子串，使得这个子串是1..k的一个排列。

昨天晚上mmd想了个n^(3/2)的算法，今天Sherlock想了个nlogn的算法。我一直在考虑有没有O(n)的算法。我觉得应该有的。
今天晚上吃饭的时候忽然想出来了。回来写了果然AC。

下面是我的算法：
注意到满足题目要求的序列必有如下性质：

1. 最大值等于长度
2. 必含1
3. 序列和为k * (k + 1) / 2
4. 序列内元素不重复

如果一个序列同时满足性质3，4，那么一定符合题目要求。
于是如果做了O(n)的预处理，可以用O(1)的时间验证某序列是否满足题目要求。
然后我的算法就顺理成章了：

1. 预处理s[i]，为序列的部分和
2. 预处理rl[i]，为从i开始往右，最长的不重复序列的末端的下标
3. 预处理m[i]，为从i开始，到i右边的第一个1（或者最右端），这一段数的最大值。
4. 枚举左端点lp，则lp到其右边的第一个1（或者最右端）中的最大值为m[lp]。把m[lp]作为序列长度，则序列的右端点为lp + m[lp] – 1。利用s[i]和rl[i]数组可以验证这段序列是否满足题目要求，若满足，就更新最优解。
5. 把输入序列反过来，重复步骤1－4。

以上每步的时间复杂度都是O(n)，故算法总的时间复杂度也是O(n)。

下面是我的代码