D1T1 Exhibition 3
一个贪心的想法是从大到小考虑所有值，每次加入最靠前的线段判断是否可行。那么要解决的问题就是用尽量少的点覆盖选中的区间。
设当前值 \(v\)，有 \(cnt_v\) 个。考虑怎么判断一个新的区间可以加入，即加入后不会改变需要的点数。这个只要对于原来的状态正反各贪心一遍，每次尽量靠后取数。那么第 \(i\) 个点的位置构成一个区间 \([p_i,q_i]\)，且有 \(q_i<p_{i+1}\)。新加入的区间只要和某一个 \([p,q]\) 有交就合法。
考虑加入一个区间 \([l,r]\) 之后怎么修改 \(p,q\)。如果 \([l,r]\) 和 \(\ge 2\) 个 \([p,q]\) 有交或者包含了某个 \([p,q]\) 就不会修改。否则一个想法是暴力更新，以 \(q\) 为例就是从 \(q\) 中最后一个 \(<l\) 的数 \(x\) 开始，每次找到所有 \(l>x\) 的区间中的最小 \(r\)，直到新的位置和原来的一样。注意到对于一个 \(i\)，\([p_i,q_i]\) 始终在收缩，所以这个的复杂度是正确的。
但是一个问题是上面的分析基于点数就是 \(cnt_v\) 不变，但是在之前的部分不能这样做，否则会破坏均摊的性质。这个其实也是容易的，只要倍增出一段使得需要点数 \(=cnt_v\)。具体地，每次先 \(+2^0,+2^1,\cdots,+2^k\) 直到 \(>cnt_v\)，然后再 \(+2^k,+2^{k-1},\cdots,+2^0\)，这样扫描的总点数就只和答案 \(ans\) 相关。
然后我们就要去动态地找第一个与所有 \([p_i,q_i]\) 有交的区间，这个不是很好直接做。观察到如果一个区间包含了某个 \([p,q]\)，那么它一定会被选，并且不会造成修改。那么可以先取出所有这样的区间，剩下的区间不包含任意一个 \([p,q]\)。此时对于一个 \([p,q]\)，另一个区间 \([l,r]\) 与它有交当且仅当 \(p\le l\le q\) 或 \(p\le r\le q\)，这个是容易线段树维护的。
https://atcoder.jp/contests/joisp2025/submissions/70516378
D1T3 Bitaro's Travel 2
观察到对于当前点 \((x,y)\)，下一步一定跳到可达点中最高的点。于是建出 Kruskal 重构树后可以倍增预处理。查询同样倍增即可。
https://atcoder.jp/contests/joisp2025/submissions/70189865
D2T1 Ambulance
在只考虑 \((1,1)\) 和 \((L,L)\) 的时候，每个点的代价只和 \(x+y\) 相关。这意味着把所有点按 \(x+y\) 排序后，存在一个分界线，左边只能连向 \((1,1)\)，右边只能连向 \((L,L)\)。
加入 \((1,L)\) 和 \((L,1)\) 后是类似的，现在就有两条斜线划分成四个部分，每个部分的中点只有两种选择。一个暴力是枚举两条线背包，复杂度是 \(O(n^3T)\)。
枚举一条斜线 \(x-y=d\) 后，另一条斜线在两边会分别划分出一段前后缀，两边分别预处理前后缀的信息即可。这样复杂度就优化到了 \(O(n^2T)\)。
https://atcoder.jp/contests/joisp2025/submissions/70197750
D2T2 Collecting Stamps 4
对于每种颜色，把它的两次出现看成左右端点，那么能凑出的种类数就是相交的区间对数。
对于一次相邻交换操作，感性理解它会且仅会使区间对数加一，那么只要枚举起点，树状数组维护出相交对数就好了。
https://atcoder.jp/contests/joisp2025/submissions/70198685
D3T1 Bitaro the Brave 3
首先一个暴力的贪心是维护一个堆，每次把惩罚最大的怪打了。
观察到贪心的过程实际上并不关心惩罚的具体值，而只关心其相对的大小关系，考虑转 01 变量。此时就是若干个怪有惩罚分 \(=1\)，最大化打掉的血量。
这个可以用二分图描述。左部点是所有有代价的怪，容量是其生命值，右部点是每个时刻。每个怪向一个后缀连边，要求这张图最大匹配。
对其使用 Hall 定理，左部点一定选的是按后缀长度排序后的一段前缀。设长度依次为 \(len_1,len_2,\cdots,len_k\)，那么就是要最大化 \(len_i-pre_i\)，\(pre\) 就是排序后一个前缀的容量和，即难度 \(\ell\) 乘上初始的和。
于是这个对于 \(\ell\) 是若干条直线求 \(\max\)，维护出凸包后对答案就是若干次区间加一次函数，差分即可。
https://atcoder.jp/contests/joisp2025/submissions/70317380
D3T2 Conference
对于每一段，它的代价只和其中的元素种类有关。如果我们确定了每一段的元素种类，那么是否合法就是一个二分图匹配问题。
记 \(len_S\) 为种类集合 \(S\) 的段的长度和。应用 Hall 定理可以发现，对于 \(x\in\left\{A,B,C\right\}\)，\(x\) 个数 \(cnt_x\) 需要在 \(len_{\left\{x\right\}}\) 和 \(\sum \limits_{x\in S}len_S\) 之间。记这个上下界分别为 \(sum_{1,x}\) 和 \(sum_{2,x}\)。
对于每一段，如果其首尾形如 \(AA\)，那么此时让其为 \(A\) 类是无需代价的。同理如果首尾是 \(AB\)，那么可以免费成为 \(AB\) 类的段。考虑从免费的情况开始调整。
当前所有 \(x\) 都有 \(cnt_x\le sum_{2,x}\)
此时只要调整下界，对于每个 \(x\)，所有 \(x\) 类的段按长度从大到小贪心即可。
恰有一个 \(x\) 满足 \(cnt_x>sum_{2,x}\)
不妨令这个 \(x\) 是 \(A\)。首先对于 \(B\) 和 \(C\)，先把它的 \(sum_1\) 调整到 \(\le cnt\)，此时一定进行 \(B/C \to AB/AC\)。然后对于 \(sum_{2,A}\)，我们有两种策略：\(B/C\to AB/AC\) 和 \(BC\to ABC\)。两者代价分别为 \(2,1\)。
考虑把所有段按照性价比从大到小排序，并贪心选择一段前缀。如果这个前缀的最后一位的代价是 \(1\)，可以说明这样就是最优解。如果最后一位的代价为 \(2\)，那么还需要考虑把代价调整小 \(1\) 的情况。此时两种方案是 删掉前面一个 \(1\)，或者删掉当前的 \(2\)，并在之后找一个 \(1\) 加入。
恰有两个 \(x\) 满足 \(cnt_x>sum_{2,x}\)
不妨令剩下那一个是 \(A\)。发现此时这个限制非常紧，因为 \(sum_{2,B}+sum_{2,C}\) 几乎取遍了所有的集合。经过一些计算，此时 \(cnt_A<len_A-len_{BC}-len_{ABC}\)。考虑先让 \(cnt_A\ge sum_{1,A}\)，此时调整量 \(>len_A-len_{BC}-len_{ABC}-cnt_A\)。
可以说明的是，我们把所有调整的 \(A\) 变成 \(ABC\) 是可以使 \(B,C\) 满足条件的。如果还有 \(cnt_B>sum_{2,B}+len_A-len_{BC}-len_{ABC}-cnt_A\)，即 \(cnt_A+cnt_B>len_A+len_B+len_{AB}\)，此时 \(cnt_A+cnt_B+cnt_C\) 大于总个数，是矛盾的。
但是如果直接调整是三倍段数，比较不优。考虑到如果有 \(A\to ABC\)，那么这一段一定是同时有 \(B\) 和 \(C\) 的。而同时有 \(BC\) 的段如果 \(\ge 2\) 个，那么就可以把一段调整成同色。于是 \(A\to ABC\) 的至多只有一段。我们只需判断能否不进行 \(A\to ABC\) 即可。
这个相当于判 \(A\) 类段按长度降序排序后，对于给定的一个前缀，能否凑出 \([l,r]\) 中的某一个元素。记 \(tim_v\) 为 \(v\) 第一次凑出的时刻，那么查询的就是区间 \(\min\)。\(tim\) 可以直接 bitset 预处理，复杂度 \(O(\frac{n^2}{w})\)。
https://atcoder.jp/contests/joisp2025/submissions/70387709
D4T2 Migration Plan
考虑一次加入的点对于一个查询的影响。因为每次修改是跳祖先，所以加入的人被推到查询点当且仅当深度相同，且初始位置在查询点的子树内。
对于每个深度维护一棵线段树，每次线段树合并即可。
https://atcoder.jp/contests/joisp2025/submissions/70388754
D4T3 Uiro
考虑从值域角度分析一点性质。
可以发现，对于一种值 \(v\)，其所有选中的位置一定形如一段后缀。设 \(p_v\) 满足 \(v\) 的 \(\ge p_v\) 的出现位置都被选，\(<p_v\) 的位置都未被选。同时如果 \(p_v>p_{v+1}\)，可以通过调整使答案不劣。
那么我们现在有 \(p\) 不减，此时对于一个 \(v\)，因为 \(p_v\ge p_{v-1}\)，所以可以认为序列是静态的，那么就可以直接二分了。
https://atcoder.jp/contests/joisp2025/submissions/70499144