题目这儿 ZCC Loves Interdiv ZCC Loves COT 首先考虑一维下的版本。（数列，区间加，区间和） 显然可以使用线段树，但是线段树推广到高维度的难度较大。 针对本题先修改再询问的特点，我们可以在修改时只保存差分后的数组。 在处理询问前求前缀和还原原数列
题目这儿
ZCC Loves Interdiv
ZCC Loves COT
首先考虑一维下的版本。（数列，区间加，区间和）
显然可以使用线段树，但是线段树推广到高维度的难度较大。
针对本题先修改再询问的特点，我们可以在修改时只保存差分后的数组。
在处理询问前求前缀和还原原数列。之后再求一次前缀和就可以做到 O(1) 回答询问了。
现在试图把它推广到二维。（三角形，子三角形加，子三角形和）
如果朴素地对每一行应用一维的差分法，最后得到的标记会像下面一样：
其中 +1 标记和 -1 标记都是连续的一段。
标记也是一种值，所以可以对标记打标记！
于是我们将所有的 +1 标记按从右上到左下做差分，将所有的 -1 标记按从左上到右下做差分。
这样每个操作实际上只需要在两个数组中修改四个值，最后利用这两个数组还原原来的标记，利用标记还原原数阵。前缀和的计算也是类似，只不过第二维的前缀和要从两个方向各算一遍。
类似地，只需要 4 个数组就可以表示三维情况下的所有标记，经过三轮不同方向上的求前缀和就可以得到原四面体，前缀和的计算也需要 4 个数组。这样单操作 / 单询问要拆成 8 个，是 O(1) 的，复杂度是 O(N^3+M+Q) 。
ZCC Loves RPG
在程序的每一个位置，都存在若干条形如 a[x]>=v 或 !(a[x]>=v) 的限制。它们给每个 a[i] 确定了一个上界和一个下界。显然，我们应当让 a[i] 尽量小，因此我们可以令 a[i] 恰取到它的下界。
那么，考虑一对上下界数列 Ui, Di ，当前语句可以被执行到的条件就是：
随着我们分析程序的过程，一些位置的下界会发生变化，我们需要随时重新计算这个最大非零子段和，这就是说，我们需要对一个数列支持单点修改和查询最大非零子段和。这是一个线段树的经典应用，这里不再赘述。
下面考虑如何分析程序。
首先需要实现一个词法分析器：它接受字符串作为其输入，每次返回一个记号（常量，符号或标识符等）。这部分可以按照写读入优化的方法来写。
然后就到了对记号流进行分析的步骤，这一步的做法有很多，这里只讲一下 std 的做法。
首先将 game(n, k) 读入，获取 n, k 的值，同时建立线段树。
清空两个栈，这两个栈一个用于保存程序结构（称为栈 P ），一个用于保存 Ui 和 Di 的变化便于之后撤销（称为栈 Q ）。
读入左花括号，向栈 P 中压入一个 B 符号， B 符号声明当前语句处于一对未闭合的花括号内，当栈 P 顶是 B 符号时，可以向这个花括号内追加语句。
随后重复以下过程直至栈 P 空。
检查栈 P 的栈顶：
若为 B ： 从词法分析器取得下一个记号。
若为右花括号：弹出 B 。（闭合花括号）
否则：把这个记号“塞回去”，向栈 P 压入 S 符号。（追加语句）
若为 S ： 弹出 S ，从词法分析器取得下一个记号。
若为左花括号：向栈 P 压入 B 符号。（新建块）
若为 cg ：读入整个 cg 语句，查询当前是否可达，更新答案。
若为 if ：读入 if 语句的第一句，读入 x, v 。向栈 P 先后压入 I 符号， T 符号和 S 符号。向栈 Q 先后压入 !(a[x]>=v) 和 a[x]>=v ，在线段树上做 a[x]>=v 的修改。
若为 T ： 弹出 T ，弹出栈 Q 栈顶元素，撤销它的修改。从词法分析器取得下一个记号：
若为 else ：应用栈 Q 栈顶元素（之前加入了但没有应用的 !(a[x]>=v) ）的修改。向栈 P 压入 S 符号。
否则：把记号塞回去。弹出栈 Q 栈顶元素，弹出栈 P 栈顶元素（必定是 I 符号）。
若为 I ： 弹出 I ，弹出栈 Q 栈顶元素，撤销它的修改。
B,S,T,I 四个符号的意思分别是：块，语句， Then 结束，整个 If 结束。
最后 输出答案。
ZCC Loves Minecraft
所求的 S 即为当前点集的正交凸包。
参见 en.wikipedia.org/wiki/Orthogonal_convex_hull 的相关介绍。直观地看正交凸包是左上、右上、左下、右下四段折线构成的多边形，每条边都与坐标轴平行。求已知点集的正交凸包，可以先找出最上、最下、最左、最右的点。求右上方的一段折线，可以从最上面的点开始，每次找当前点右边的点中最上面的点，与当前点 L 形连接，作为新的当前点，不断重复直到选到最右边的点。这一过程实现非常简单，只要先按横坐标排序，然后扫描一遍并维护纵坐标最大值即可。其它三段的求法是类似的，而且可以通过旋转进行转化。那么对于动态加点的问题，可以用 4 棵平衡树（实现用 STL 即可）分别维护四段折线。插入点时尝试将其分别插入四段折线的相应位置，若在当前折线外部需要更新折线，并计算面积的增量。以右上折线为例，需要不断判断新点左边的点是否在新点下方，若是则删除。由于每个点最多被插入一次删除一次，总的时间复杂度是 O(nlogn) 。边界情况需要一定的特判。
ZCC Loves words
这道题我们可以先对单词建出 AC 自动机。然后在 AC 自动机上进行计数（ dp ）。 F[i][j] 表示当前长度第 i 位，当前在 AC 自动机的 j 号节点。我们考虑主动转移，如果 j 号节点在接受 c 这个字符后到了第 k 个节点，那么 F[i+1][k]+=F[i][j]*Get 。其中 Get 表示在第 k 个节点能乘上的数字。
我们来分析一下 Get 。 ，那么如果没有 + i 这个东西，我们就可以建出矩阵，然后直接快速幂 + 矩阵乘法。但是有了 + i 的话，每个矩阵都不同，但是事实上 P= 179 * 173 * 163 ，这其中的质数非常的小， 然后就是乱搞的部分了， i Mod Pi 就是 O(Pi) 的循环，于是我们建出 Pi 个矩阵，然后对于 L/Pi 的部分快速幂 + 矩阵乘法，对于 L Mod Pi 的部分暴力矩阵乘法即可。对于每一个质数得到的答案，利用中国剩余定理就可算出最后的答案。复杂度大概是 O(Pi*tot^3 + log(L)*tot^3) 。
如果有更优的做法欢迎指教。
ZCC Loves cards
ZCC Love ranklist
第一问：
当 k=1 的时候答案显然为 n-1 。
当 k=2t （ t ∈ Z* ）时答案显然为 0 。把比赛分成两两一组，每组和为 n+1 即可。
当 k=2t+1 （ t ∈ Z* ）时先两两一组到只剩 3 个。 n 为偶数时答案显然不能为 0 ，只能做到 1 。奇数时则可以做到。一种解决办法是：
n 为奇数
1
4
7
n 为偶数
1
4
6
2
5
5
2
5
4
3
6
3
3
6
2
4
7
1
4
1
5
5
1
6
5
2
3
6
2
4
6
3
1
7
3
2
第二问：
先观察进步指数的性质：由于 NewRank=OldRank 的时候进步指数 =0 所以 只能出现一次所以不应该使用。 当 NewRank ! = OldRank 的时候 两个进步指数相等当且仅当 NewRank 和 OldRank 都相等，两个进步指数为相反数当且仅当 NewRank1=OldRank2 ， OldRank1=NewRank2 。
总共能出现 n*(n-1)+1 种不同的进步指数，而且 n>1 ，所以每种进步指数（除了 0 ）都会出现。并且进步指数为相反数的一对只能出现在同一场考试中。所以 n 为奇数时显然无解。
当 n 为偶数时，注意到每场考试实际上是将考生两两组队 n-1 轮且不重复。于是使用循环赛构造算法即可。
循环赛构造算法： http://www.doc88.com/p-694165485213.html
ZCC Love march
我们用 set 维护当前的士兵位置，合并的时候 将每个 士兵暴力合并到该位置， 即 删掉原位置士兵并使目标位置 size+= 原位置 size 。每次移动的时候 将 原位置 size-- 并 在 新位置新建一个 size 为 1 的 士兵 。 这样 最多只会有 n+ 移动数 的士兵，每 个 士兵只会合并一次，所以时间复杂度为 O(nlo gn) 。实现的时候 为了记录每个点 的坐标 可以用并查集维护所在的块 。
ZCC Love traffic lights
首先考虑如果是一般图的话怎么做。可以证明存在一个最优解在某一条边上卡着时间进去或者卡着时间出来。因为如果不这样的话可以将每个点的时间往后推直到卡着时间。所以只要对在每个点上卡时的情况进行判断。
枚举了某个点的到达时间以后那么接下来我们可以使用最短路算法求出到终点的最早时间和从起点出发的最晚时间。具体实现的时候可以对每个点开 8 个状态记录从哪个方向进入和是否闯过红灯。
ZCC loves Army
Solution ：
可以发现上司和下属之间的关系可以构成一棵树，考虑三种操作。
交换下属：为了使交换下属的时候改变的边变少，可以用左儿子右兄弟的方式表示这棵树。那么交换时只需要改变至多 4 条边。可以用 LCT 维护。
传送信息：求从 x 传信息到 y 所需要的中介人的最少个数。令 x 为深度较大的一个点，这条路径就是 x 向上传到和 y 同一层，再水平传送。可以把编号为 1 的儿子的权值赋值为 1 ，求 x,y 简单路径上的权值和。
发送指令：求 x 可以收到几个士兵发出的指令。表现在左儿子右兄弟的树上即为求该点到根之间的点个数。
Postscript ：
为了方便，可以给每个点加一个编号为 0 的虚孩子，可以避免一些细节问题。
交换下属的时候找孩子可以对每个点开一个平衡树，也可以直接用 LCT 里的 Splay 。
ZCC loves Codefires
考察序列中相邻的两题 i, j(i 在前 ) 。交换它们后，解出它们之前的题目所带来的时间对答案的贡献是不变的，它们对它们后面的题目的贡献也是不变的，其他题目之间对答案的贡献自然也是不变的。唯一的变化就是，原来的 EiKj 一项变成了 EjKi 一项。那么，为了使答案变优，需要满足的条件是 EjKi ≤ EiKj 。也即 Ei/Ki ≥ Ej/Kj 。
那么，最优解序列 Ai 一定满足， EAi/KAi 是递增的。
排序一遍即可。