感觉比 年的题目简单一些，能自己做出一些题目。

这里有除了 【IOI 热病】 的所有传统题的题解。

Day1T3 饮食区

这道题再次说明 JOISC 的题目排序是乱序的。

题意： https://loj.ac/p/3489

容易发现，如果我们能求出这个队列目前一共 pop 掉了多少人，那么我们进行整体二分/可持久化线段树+二分就可以求得答案。

而求出 pop 掉多少人等价于求出这个队列现在有多少人。

观察队列人数的变化，注意到操作 相当于区间加/区间减，同时每次操作后对 取 。

当时脑子烧了，想了一个 的分块。实际上，Seg beats 就可以做这个。然而，因为是区间操作，单点询问，我们甚至不需要 Seg beats，只需维护一个二元标记 表示 ，给线段树上对应节点打标记即可。

时间复杂度 。

代码： https://loj.ac/s/1777073

Day2T2 道路建设

题意 : https://loj.ac/p/3491

做完这题才意识到我两年前好像见过这题。

欲求前 小，先求第 小。

求第 小需要二分，即找到有多少对点之间的距离 。

此时曼哈顿距离就不大好做了，考虑将坐标系旋转 （即 ），此时原图的曼哈顿距离是新图的切比雪夫距离，即 。

那么 就等价于 。

那么把点按 坐标排序后，用一个 set 维护所有跟当前点 坐标相差不超过 的点集即可。

在找有多少对点的距离 的时候，我们顺便把所有 的点对都扔到一个答案数组里，这样在二分得到第 小的时候，也顺便把前 小都找出来了。

时间复杂度 。

代码：https://loj.ac/s/1777222

Day3T2 保镖

题意：https://loj.ac/p/3494

神仙题，主要是第一步难以想到。

考虑保镖和人相遇需要时间和位置都重合，在一维的数轴上不好做，不妨以坐标和时间为两维建立坐标系，将问题变为二维。

此时每个人相当于一条斜率为 或 的线段，保镖的行走路径则是摇摆着向上的折线。

图还是不大美观，考虑将坐标系旋转 ，此时每个人变为一条横线或一条竖线，保镖则是只能向右或向上走，想要最大化小费。

注意到在两次变换之后，新图中两点之间的距离被拉长至原图的 倍，所以 要除以 （这就是为什么 是偶整数）。

此时所有人的轨迹可以交织成一张网格图。如果保镖从一开始就在网格图的格点上，那么答案其实是容易算的。设 表示从网格图中的点 出发能得到的最大小费，转移是简单的。

问题在于保镖一开始可能落在某个小网格的中间。

考虑此时保镖的决策，一定是先向上走一段，走到某条格线，然后向右拐走到一个格点。也可能先向右再向上，这是对称的。

此时，保镖走的第一段路是没有贡献的。设其走的第二段路权值为 ，长度为 ，走到了格点 ，那么贡献是 。

对于一个 ， 和 都是确定的，这个式子就是一个关于长度的一次函数。我们回答询问，就是对于一个一次函数序列的前缀，查询某个横坐标对应的最值。

显然，使用李超线段树即可做到 。

其实还可以做得更好。

注意到 值是具有单调性的，即 。而 值就是一次函数的截距，而如果一个函数的斜率和截距都不超过另一个函数，说明该函数已经没有用了。据此我们可以维护一个斜率递减的单调栈，因为我们可以保证每次插入的直线的截距都是当前最大的。维护单调栈时再把不符合凸性的直线弹出 ，我们就可以均摊 的维护一个凸壳。查询时在凸壳上二分即可。

实现的时候可能要把图像按 轴对称，因为斜率递减的话，我们相当于是从右往左的维护了一个凸壳，不大方便。对称过后即使正常的从左往右维护凸壳。其实不这么做问题应该也不大。

时间复杂度 。

代码：https://loj.ac/s/1778383

Day3T3 聚会 2

题意：https://loj.ac/p/3495

比较单薄的题，看出来就做完了。

考虑两个相邻的点 均为重心是什么情况。

那一定是 对应的子树有 个关键点， 对应的子树也有 个关键点。这样把重心从 调整到 ，总边数才不会变。

为奇数时肯定没有这种情况，所以答案为 。

为偶数时，也可以用上述的调整过程说明，那些重心一定形如一条链（因为如果调整到这条链以外，代价肯定会变多），而链两端对应的子树都有 个关键点。

考虑选出一条链 ，它能贡献不超过 的 。我们可以直接将贡献记在 上，最后对答案数组做一遍后缀 即可。（ 和 分别是有多少点位于链的两端）。

这个问题使用点分治+树状数组即可做到 ，实现细节可参阅代码。

代码：https://loj.ac/s/1777442

Day4T1 聚会 2

题意： https://loj.ac/p/3496

还是差了一步，说明大脑没有完全恢复。

看到字典序最小考虑贪心，显然我们的策略是从 到 考虑每个区间能不能放，能放就放。

设 表示只考虑 中的位置，最多能放多少个区间。

那么假设我们选了个区间 ，其将其所在的空段 变成了两个空段 和 （空段就是其中没有被选的区间或其一部分的段），那么我们能选当且仅当选完之后仍然可以选出不少于 个区间。设原来答案为 ，则能选当且仅当 。

我们发现只要快速算出 ，就能快速判定一个区间的可选性。

考虑 时，我们可以设计一个 ，设 表示 是所有选的区间中最靠左的那个时的最大区间数。考虑紧邻 的那个区间，一定是满足 且 最小的区间 。那么有 。

我们发现，对于一个 只会有一个唯一确定的 （其实可能有多个，但它们的 相同，故都是等效的）。

因此我们完全可以通过倍增来计算 DP 值，在 不确定时，我们找到最靠左的那个区间，然后倍增直到右端点 即可。

时间复杂度 。

代码：https://loj.ac/s/1777788

Day4T3 最差记者 4

题意： https://loj.ac/p/3498

首先连边 ，形成一个拓扑图。显然这会形成一个根向基环森林，而环上的权值应当全部相等，且要么是 要么是环上的权值。

考虑树的部分怎么做，一个暴力的想法是设出 DP 状态 表示处理 子树内的情况， 点本身权值为 的最小代价。那么有转移方程： 显然我们不可能暴力实现，只能采用数据结构维护。而 的限制很烦。注意到 是个定值，我们修改状态的定义，设其为最大可以节省多少费用。这样转移就变为： 这样我们在数据结构中就只需要单点修改，而非修改两段区间。

说到这里，用什么数据结构也就基本呼之欲出：线段树！

我们使用线段树合并维护每个点上的 DP 值。

你会发现我们需要在线段树合并时处理后缀 的问题。

这也好办，在合并时记录两个变量分别表示这两棵线段树在 上的 ，合并时先递归右边，再递归左边即可。

在有一个当前节点为空时，需要将维护的后缀 加到另一个当前节点对应的所有位置，这需要一个加法标记来实现。

牵扯到标记就会有一个问题：如果标记下传到一段没有节点的区间，我们要怎么处理？

其实在这道题中是不需要处理的。因为实际上 ，DP 的第二维取到的只能是子树内的点权。而子树内的点权对应的位置在单点修改的时候就已经为其新建了一些节点，所以这种情况实际上不会存在。

这也解释了为什么之前要将 DP 状态进行一个小变化。变化之前我们并不能保证子树内的点权对应的位置均被新建了节点。

做完树的部分之后，环的部分只需要枚举环上点的取值即可求得答案。

时间复杂度 。

代码 : https://loj.ac/s/1777827