也是赤裸裸的Splay，和前面两题平衡树的一样，都是求最小插值。因为加了绝对值，所以往根左右两棵子树考虑。

因为在收养所里面的只能都是人或者都是宠物，所以在平衡树里面加一个TreeType表示树里面存的是什么，0就是宠物，1就是人，2就是空。如果进来的类型跟树的类型相同，那就插入节点，否则从树中找到一个差值最小的节点并删除。

删除操作很容易错，因为这个调了半天，整体上的思路就是把待删除节点提到根，然后合并左右子树。麻烦的就是一定要把跟待删除节点的联系全部切断，否则经过旋转平衡树会“很没有节操”，也就是不满足BST的性质，而且你会发现这个被删除的节点又出现了，而且有的节点六亲不认……

Splay要注意，每个操作之后都要旋转到根，这样效率差很多，一开始我把Max()和Min()中旋转的两句话给去掉了，结果TLE，加上去后明显快多了。

基本上这题还是被用来熟悉Splay，确实写了这三题对Splay就熟悉多了，哪天写Splay写的跟快排一样那就达到目的了^_^。现在习惯了把左旋右旋合并在一起的文艺青年的写法，代码短很多，就是不好理解。不过可以先背下来，就像快拍一样，到某个时候自然就顿悟了。 Read on →

考察的就是平衡树，这里选用的是Splay，需要插入、删除、查询第k大这三个操作。

由于工资的变动是对全体员工的，所以可以设一个变量Delta，记下相对于第一个人进公司时的工资差。那么当来一个工资为x的员工的时候，就在平衡树里面加上x-Delta的节点；查找到树内第k大的数为x，那么该员工的工资就是x+Delta。提高全体员工工资就只需要+Delta，降低就只需要-Delta。

不过当某个员工的工资低于最低限额的时候他就会离开，也就是树内所有小于min-Delta的点都必须删除。因此这题删除节点的方法比较简单，和Splay一般的Delete不大相同，只需要插入一个min-Delta-1的节点，把它提到根节点，接下来只要把根的右子树当作根就行了。

为了防止节点重复出现，可以在树的节点中多记录一个count表示和这个点大小一样的点有几个。至于查询第k大的值，可以在树的每一个节点中多记录一个size表示这个点及以下有多少节点，那么根据这个size，从根出发就可以找到第k大的节点了。

这题要特别注意的是，刚进来的时候工资就低于下限的话，不计入公司人数和离开人数，相当于打个酱油就回去了。 Read on →

一条线段关于特定直线的投影是指：分别从这条线段的两个端点对特定直线作垂线，两垂足之间的距离就是其投影。

如果有一条直线穿过了所有已知线段，那么作任意一条垂直于该直线的直线L，则所有线段在L上的投影必定有交点。因此这题就是求是否存在一条直线穿过所有已知线段。那么问题是怎么枚举这条线段呢？

可以注意到，若在由平面上的任两点确定出的所有直线中，不存在符合要求的直线那么在平面中肯定不存在符合要求的直线。因此，我们只需要用题目所给的2n个点，两点确定一条直线，验证这条直线是否穿过所有线段即可。

验证一条直线是否穿过一条线段比验证两线段相交简单多了，只需要考虑线段是否跨过线段即可。利用叉乘即可解决。

注意数据中存在在精度之内的相同点，组成直线的时候要注意此时不能取。 Read on →

基本上同PKU2318。不同的地方在于读入的分割线段是无序的，需要先排序才能二分；统计的对象稍有变动。 Read on →

题目大意就是说一个矩形被不相交线段分割成了几块，有些点落在里面（不会落在线段上），统计每一个区域里面有多少个点。

这题就是叉积的典型应用。因为线段不会相交，所以一个点在哪个区间里面，只需要知道它在哪两条中间就好了。朴素的做法就是枚举线段，这样需要O(nm)的时间。其实可以用二分优化，不断往右找，直到找到一条在当前线段的右边的最靠左边线段，那么这个点就在这个线段和上一条线围成的块里了，复杂度优化到O(nlogm)。 Read on →

题目就是求封闭图形的面积。

如果一个封闭图形按照一定顺序的点集P={(x1, y1), (x2, y2), …, (xn, yn)}，那么其面积就是几个向量积的和：S=|0.5*((x1, y1)×(x2, y2)+(x2, y2)×(x3, y3)+…+(xn, yn)×(x1, y1))|。因为题目是给定一条路径生成多边形，所以根据读入顺序就保证了边的顺序，就不需要进行极角排序了。 注意，这题没必要用，因为小数位只有可能为.5，只需要根据S奇偶性特判就好了 Read on →

这题求的就是一个凸包的周长再加上一个给定半径圆的周长（因为凸多边形的外角和=2pi）。可以作为凸包算法的模板。

这里用的是一种叫做“单调链法”的方法。先将所有点按照x坐标从小到大排序；然后从1到n线性扫描一遍，确定凸包的上壳；接着再从n到1扫描一边确定凸包的下壳。为了方便修改线段，所以可以将构成凸包的点按顺序存如一个栈中。 Read on →

题目是求环状序列A的一段长度>=k的子序列，使得子序列的和最大。

因为是的环状的，所以将其长度延长k-1。用sum[i]表示a[1]+…+a[i]，题目转换成求最大sum[i]-sum[j-1]。因为sum[i]是固定的，因此选择最小的sum[j-1]。不妨考虑用单调队列来优化，维护一个单调递增的队列，记下sum[j-1]，每次用队头来更新最大值。 Read on →

将所有矩形按照长度l[i]从小到大排序，用f[i]表示买下前i个矩形的最小花费，那么容易得到方程f[i]=min(j=0->i-1,{max(k=i->n, {w[k]})*l[j+1]+f[j]})，复杂度为O(n^2)。

考虑把所有矩形看成直角坐标系中的点Pi(l[i],w[i])，那么显然如果对于点Pi存在某个点Pk使得l[k]>=l[i]&&w[k]>=w[i]，那么矩形i将没有意义，只要买下了矩形k就必然买下了矩形i，因此可以将矩形i删去。删掉多余点后，会发现各个点的纵坐标是单调递减的！

按各点x坐标排序，这样一来动规方程就变为了f[i]=min(f[j]+x[i]*y[j+1])。可以证明，f[i]是单调递增的（例如用四边形不等式）。这样就转化成了1D1D动态规划的最简单模型了。

使用一个队列保存每一个决策控制的下标范围，用二分查找来更新范围，总的复杂度降至O(nlogn)。 Read on →

此题作为陈丹琦《基于连通性状态压缩的动态规划问题》的例题1，主要的思想是扫描线、插头和括号匹配。具体的思路借鉴陈丹琦《基于连通性状态压缩的动态规划问题》。

扫描线采用三进制存储，第0_{m-1位对应扫描线0}m-1位置上的上插头，第m位对应左插头。虽然使用四进制可以使用位运算，但四进制状态数过多，达到4^13，必须使用hash，否则空间难以承受，这样一来四进制倒不一定比三进制快。使用一个队列记录下上一次状态更新过哪些节点，这一次的状态从当中更新即可，这样省去了枚举上一次的状态，节省了不少时间。另外，对于括号的匹配，虽然预处理之后DP只需要O(1)即可完成转移，但会大大增加代码长度和内存使用，不如到DP的时候再进行扫描，反正也只需要O(m)的时间。 Read on →