为了让题解集合不显得太臃肿，代码托管到了第三方上面。
Day1
特技飞行
又是提答又是计算几何，注定很少人会去写它
IOI 热病
咕掉惹。
饮食区
考虑如果我们可以去除“离开”操作的影响，假装没有人离开并修改“服务”时候的查询参数，那么也可以解决问题。
假如没有人离开，那么就可以使用整体二分解决这个问题。
现在有人离开，假如不存在某次队列全部清空的情况，那么可以直接让询问的 (B) 加上离开人数从而去掉离开的影响。
假如存在清空的情况，那我们需要统计实际离开人数。假设对于商店 (A)，目前有 (n) 次人数变化，它第 (k) 次人数变化量为 (delta_k)（使用正负标注“离开”或“加入”），那么当前实际人数为：
由于 (delta) 是按照时间排序的，因此可以按照时间，用线段树维护每个位置上人数变化的前缀和最小值。知道了实际人数，也就不难算出“服务”的具体参数了。
Day2
逃跑路线
目前只能在 JOISC 官网上面下载题目文件。OJ 上还没有测评包。
道路建设*
鉴于 (K) 比较小，因此可以想到用堆维护每个点的最近点对，并按顺序取出前 (K) 小的点对。
为了保证不会重复计算，对于标号为 (i,j(i<j)) 的点，我们只会在 (j) 上计算 ((i,j)) 的点对。
一个比较**的做法是，将曼哈顿距离转化为切比雪夫距离，那么查询最近点对可以使用二分+二位数点，可惜是 (O(nlog_2^2n)) 的。
另一个更加厉害的做法是，直接用 KDT 维护最近点对！这个我不清楚啊，看别人写的
真正的做法：
由于计算点对已经有了有序性，利用这个有序性我们可以顺便拆掉一个绝对值。比如，将所有点按照 (x) 排序就可以去掉 (x) 上的绝对值。那么我们只需要处理 (y) 一维的绝对值，这个按 (y_1,y_2) 关系分类后利用线段树完成。
考虑到每次加入点和每次删除点对都只会修改一个位置，我们可以使用可持久化线段树维护前缀可用点。
删除需要注意。最值本身不支持直接删除，但考虑线段树的叶子上已经保证了 (y) 相等，而 (x) 又是从小到大有序的，所以对于一个叶子而言，该位置上的前一个版本的信息一定就是删除该点对之后的最大值，所以读取前一个版本的信息即可。
小结：
- 看到“绝对值”这样的信息，应该要注意分类讨论，而非盲目地转化成切比雪夫距离；
- 主席树删除用到的小技巧可以注意一下。
购物
目前只能在 JOISC 官网上面下载题目文件。OJ 上还没有测评包。
Day3
古老的机器*
人生中第一道通信题，献给了 JOISC 2021 的这道题目
30 pts
首先需要知道如何不得到 Wrong Answer [6]：
考虑最左边的一个 (X)，如果移除顺序合理，它是可以被共享的。
将该 (X) 之后的序列按照 (Z) 分段，并且分段处理，每一段在处理完之后需要保证完全被移除。那么，每一段上就只可能有 (X) 或者 (Y)。对于连续的一段 (Y)，选取其中的任意一个留在最后移除效果都一样；而对于连续的一段 (X)，我们可以让它们在右边的机器全部被移除之后再移除它们，一定是最优的。
为了简化操作过程，我们从左往右移除段，每一段上先从右往左逆向移除 (X,Y)，最后再将 (Z) 删除。可以发现这个过程是符合上面的分析的。
Anna 只需要每两位描述一个机器的型号，将信息传给 Bruno，剩下的交给 Bruno 就可以获得该部分分。
现在的空间利用比为 1 : 2。
40 pts
由于每一位只有 (3) 种情况，使用 (2^2) 的状态描述太浪费了。
注意到 (log_2 3^n=log_2 2^{nlog_2 3}approx1.6n)，因此我们可以代入得到 (3^5) 应该与 (2^8) 接近。
实际上也确实如此，(3^5) 略小于 (2^8)，因此我们可以用 8 位二进制压缩 5 位信息。只需要利用 (1.6n) 位即可完成任务。
现在的空间利用比为 5 : 8。
70 pts
Bruno 实际上只需要知道第一个 (X) 的位置和之后的 (Z) 各自的位置就可以知道如何操作。我们可以将这些位置用 1 标注，这样他就可以自己识别了。
现在的空间利用比为 1 : 1。
100 pts
这个优化就比较厉害了
考虑到连续的一段 (Z) 实际上意义也不大，除了最右端的 (Z) 以外前面的 (Z) 也没啥用。那么我们就可以只在最后的这个 (Z) 上做记号。
这样的传输信息有啥特点呢？很重要的性质就是除了第一个 (X) 与第一个 (Z) 以外，剩余的 1 不可能相邻。
这样的序列的数量是多少呢？通过各种方法可以算出，长度为 (n) 且无相邻 1 的序列数量为 (f_{n+2})，其中 (f_k) 为 Fibonacci 数列的第 (k) 项。
嘛，(f_{n+2}) 肯定还是会比 (2^n) 小一些的。打表观察又可以发现 (f_{63+2}) 略小于 (2^{44})，因此我们可以选择用 44 位二进制压缩 63 位信息，那么只需要使用约 (frac{44}{63}n) 即可解决问题。
有一个小细节，为了避免第一个 (X) 与第一个 (Z) 的 1 连续，我们可以在第一个 (X) 之后插入一个 0 来处理。这样基本不会影响整体操作。
现在的空间利用比为 63 : 44。
小结：
-
压缩信息的通信题目，目的就在于提高空间利用比。
对于 Anna 而言，作为信息发出端，她需要做的是：
-
让同等长度内的字符串装下尽可能多的信息。
例如，从 1 : 2 提升到 5 : 8 的过程中，原先的 (3^4) 装进 (2^8)，显然没有 (3^5) 装进 (2^8) 划算。
由于字符串的信息通常是指数级的，因此这通常是在函数上找整点的问题。
-
通过优秀的编码方式来表示信息。
例如，从 1 : 1 提升到 63 : 44 的过程中，已有的 (2^n) 对于有效信息来说还是浪费；给有效信息合理编号从而压缩标号的值域才能成功地减少所需长度.
对于 Bruno 而言，作为信息接收端兼操作端，他需要做的是：
-
明确如何操作。
-
简化操作从而简化需要的信息。
同样是 1 : 1 提升到 63 : 44 的过程中，部分 (Z) 的信息已经被省略掉了，才能相应地减少有效信息。
-
-
任何有意义信息的基础都是有效编码。在二进制字符串中，可用码很少，因此需要充分利用字符串的附加信息，例如编码格式。所以在实际操作过程中一定需要注意设计好格式。对于字符串而言，字符串内容是明面信息，而字符串格式更是重要的隐含信息。
保镖
又咕掉惹
聚会 2
为了方便虚树，下面称居住点数目为 (k) 时的答案为 (f_k)。
以出席者的居住点构建虚树，那么满足条件的开会点就是树上带权重心。
如果带权重心是一个点那没什么可说的；如果是一条边 ((u,v))，那么满足条件的点的数量为 ((u,v)) 两点在原树上的距离 +1 。
什么时候重心在边上？当然是这条边左右子树大小一样的时候。回到原树上来，如果 ((u,v)) 想要成为虚树上的重心，那么就必须存在一种方案使得以路径 ((u,v)) 为根的时候，(u) 的子树内和 (v) 的子树内可以选出同样多的居住点来。
设此时 (u) 子树大小为 (s_u)。上述条件意味着 ((u,v)) 可以贡献到 (f_{2k})，当且仅当 (kle min{s_u,s_v})。
那么问题就方便多了。对于 ((u,v))，我们可以将它贡献到 (g_{min{s_u,s_v}}) 去，那么 (f) 就可以由 (g) 在 (O(n)) 的时间内计算出来。
此外，由于 (u) 的子树大小取决于 (u,v) 之间的相对关系，我们需要分类讨论：
-
如果 (u,v) 之间存在祖孙关系：
这个时候不妨设 (u) 是 (v) 的祖先，唯一需要注意的是 (u) 的子树大小会发生改变。
我们在 (s_u) 成为较小值的时候统计一遍 ((u,v)) 的信息，此时是按照 (s) 的大小查询子树信息；
我们还在 (s_v) 成为较小值的时候统计一遍 ((u,v)) 的信息，此时可以逆序枚举 (s) 并进行祖先查询；
-
如果 (u,v) 之间不存在祖孙关系：
那么 (u,v) 的子树大小都不会有变化。
可以在 (operatorname{LCA}(u,v)) 处统计信息。那么就不难想到设 (dp_{u,i}) 表示 (u) 的子树大小为 (i) 的子孙的最大深度。
转移可以直接线段树合并，贡献相当于做了一次 (min) 卷积，维护一下后缀最大即可。
注意：线段树合并的时候，遇到了空结点需要将已有的后缀信息在非空结点上打上“贡献”标记，避免漏掉贡献。
小结：
- 一定要想清楚之后再开始写代码，不要急急忙忙导致反复重构！
- 线段树合并的时候不要漏掉了贡献。
Day4
活动参观 2*
求字典序最小不难想到从小到大枚举每个活动是否能加入到“必选”活动中。
如何检查？考虑当前活动时间为 ([l,r])，如果它不与其他必选活动相交，那么它就会被包含在空闲时间段 ([L,R]) 中，也即 ([l,r]subseteq [L,R])。此时 ([L,R]) 会被拆分成两个新的时间段 ([L,l]) 和 ([R,r])，因此我们只需要能够快速求出任一空闲时间段的最大活动数即可。
一般我们会采用 (O(n)) 的贪心处理。但是，贪心一般意味着一些较简单可叠加的操作。例如，询问空闲区间 ([p,q]) 时，我们会在可用活动中选取右端点最小的，例如 ([a,b])，之后的操作就相当于继续对 ([b,q]) 进行询问。
由于 ([a,b]) 的选择与 (p) 有较大关联，因此我们可以设 (f_p) 为满足 (ple a) 的活动中的最小的 (b)。那么询问就相当于反复跳 (f_p)，因而可以使用倍增优化。于是单次查询就变为了 (O(log_2n))。
小结：
-
对于倍增的适用范围要足够熟悉，它通常是处理一些相似、重复的行动，例如指针跳转。
由于部分贪心操作相对简单，倍增也常常可以用于优化贪心；
-
应当分析一些贪心操作的本质；
向导 2
目前只能在 JOISC 官网上面下载题目文件。OJ 上还没有测评包。
最差记者 4
草系列题目怎么都出到 4 了
考虑从 (i) 向 (A_i) 连边，最后一定可以得到一棵基环内向树。
这里列举一些简单的性质：
- 根据边的含义可以知道环上的点最终 rating 相等；
- 修改后的 rating 总可以是初始 rating 之一，因此初始 rating 是可以离散化的；
- 我们可以反过来求没有修改的选手的 (C) 之和的最大值，下文称“没有修改的选手的 (C) 的和”为“贡献”；
考虑特殊的树的情况：树上就可以 DP 了，比如设 (f_{u,i}) 表示当 (u) 的 rating 为 (i) 时的最大贡献。
可以目测出 (f) 的转移为：
如果暴力做是 (O(n^2)) 的。
注意到转移中复杂的地方就是 (max_{ile j} f_{v,j})，如果我们能快速维护它就好了。
为此，我们设 (g_{u,i}=max_{ile j}f_{u,j})，并研究一下它的性质：
-
(g_{u,i}) 随 (i) 增大而不增；
-
(g_{u,i}) 是分段的；
-
如果将 (g_{u,i}) 和 (g_{v,i}) 对应位置加起来：
其中的蓝色实线表示 (g_v)，红色虚线表示 (g_u)，紫色点线表示 (g_u+g_v)。
可以发现 (g_u) 和 (g_v) 的差分也是对应相加的，并且与一般的 (g) 一样也具有相似形式。
-
在转移中，(sum_{v}g_{v,i}) 是具有相似形式的，我们考察在 (H_u) 的位置单点加上 (C_u) 之后对 (g_u) 的影响：
可以发现此时是从 (H_u) 开始向前，将一段推平。如果考虑 (g_u) 的差分，那么相当于找到最大的 (l)，使得 ([l,H_u)) 的差分之和大于 (C_u)，之后便会将 ((l,H_u)) 的差分推为 0，并且修改 (l,H_u) 的差分值。
通过上述分析，我们可以发现 (g) 的差分可以很方便地使用线段树维护。
这便是树上的解法；基环树上也并不复杂。将环上的每棵树都做一遍 DP 之后合并。由于这里的 (f) 并没有做后缀 (max)，所以需要枚举最终环上的权值并计算最大贡献。
时间复杂度可以是 (O(nlog_2^2n))，也可以是 (O(nlog_2n))。
小结：
- 运用函数思维、几何方法，分析 DP 数组的性质从而利用数据结构高效维护；
- 补集转化的思想，大大简化了问题；