由于本人分治很菜，所以就来刷分治题了。
先思考 50 分\(O(n^2)\)的做法。记录每一个位置的原始值、变化后的最大值、变化后的最小值，然后发现如果一个位置\(i\)对后面的位置\(j\)有贡献当且仅当：
\[a_i < minVal_j \ (1) \\ maxVal_i < a_j \ (2) \]
所以这就相当于一个二位偏序的题目，有两个限制。我们可以用整体二分，在做完左区间之后，左区间按原来的值进行排序，而右区间按最小值进行排序，即可满足第一个条件；第二个条件可以用线段树来搞，搞两个指针来比较大小，然后用线段树来统计答案即可。非常好写。
这道题真的是令人窒息，也告诉了我比赛的时候上 QQ 是一个非常坏的习惯。
这道题 60 分做法非常之显然：相同体积的物品归为一种物品，且价值为同体积内最大的价值。这样就可以把物品数量压到 100 个以内。
但是这样是通过不了全部分数的，而且全部分数的容量非常之大，所以正常的 DP 优化是行不通的。做完上面的压缩之后，可以考虑做一些贪心进行优化。接下来我会详细的介绍这个贪心策略：
LCT (Link Cut Tree) 是一种维护树链的灵活的数据结构。与线段树不同的是，LCT 一般使用 Splay 这种非常优雅、灵活的数据结构来维护树链。因为 LCT 支持动态增边、删边，所以很多题目就可以打破一些限制进行求解。
真难。
简单来讲，题目要求满足\(\{x_i \mod m \in [1, m – 1]\}\)的\(k\)元组个数。我们可以先把\(x_i\)全部模上一个\(m\)，然后令\(A = \sum_{i = 1}^k (x_i \mod m)\)（注意，\(A\)并没有被整体取模，只是各项余数之和），可知\(A \mod m = n \mod m\)，且\(A\)的上限就是\(A = k(m – 1)\)（各项上限）。
我们做了这样一个设置之后，问题就可以转换为：对于每一个不同的\(A\)，满足\(A \mod m = n \mod m\)且\(A = \sum_{i = 1}^k (x_i \mod m), \forall i, x_i \in [1, m – 1]\)的\(k\)元组方案数。首先，我们可以先枚举每一个\(A\)来缩小问题的范围，根据\(A\)所满足的条件，可以这样遍历\(i\)来获得每一个\(A\)：
这道题挺好的，让我知道了线段树还有这样的操作。
考虑线段树维护一段区间行入口到行出口的最短路，大概的维护方法非常像 Floyd。也没啥好说的，看代码吧。
这道题二次函数的暴力分有 60 分，正解来自于论文。
这道题的主要是利用了一个结论，并且运用了辗转相除法的一种思想来对问题进行化简。首先，我们把向量调整至同向，且使\(|\vec{a}| < |\vec{b}|\)，然后再来推导一个结论：
结论 对于\(\vec{a}, \vec{b}\)，如果\(<\vec{a}, \vec{b}> \geq \frac{\pi}{3}\)，那么答案就是\(min\{|\vec{a}|, |\vec{b}|\}\)。
这个结论的证明参见《欧几里得算法的应用》。所以，我们就可以大概知道，我们可以将较长的向量分解：\(\vec{b} = k\vec{a} + \vec{b’} \)。由于我们知道，这道题可以笑掉这个\(k \vec{a}\)，所以就可以用辗转相除法的套路进行处理。具体见代码：