JOISC2022 Day1 监狱 Jail
首先我们发现操作一定是给所有人排序，然后按照顺序直接从 \(s_i\) 挪到 \(t_i\)，要求是对于 \(i\)，所有在它之前挪的 \(t\) 不能在 \(s_i\to t_i\) 上，所有在它之后挪的 \(s\) 不能在 \(s_i\to t_i\) 上。有了这个条件我们就可以 \(O(n^2)\) 建图。但是这样太慢了，考虑优化建图。对于路径 \(i\)，\(u\to v\)，设 \(u\) 下一个点 \(u'\)，\(v\) 前一个点 \(v'\)，那么建立点 \(S_1,\dots,S_n\) 和 \(T_1,\dots, T_n\)，那么连边 \(T_u\to i\)，\(i\to S_u\)，\(S_{[u',v]}\to i\)，\(i\to T_{[u,v']}\)，这个建边可以用树剖线段树优化建图。然后再跑一遍拓扑即可。
https://qoj.ac/submission/105989
JOISC2022 Day1 错误拼写 Misspelling
首先我们转化一下条件。对于条件 \((i,j)\)，如果 \(i>j\) 那么就代表 \([j,i]\) 区间内的字符串要么全相等，要么第一段连续段的字符比第二段连续段的要小，称其为第一类限制；如果 \(i<j\) 则代表要么全相等，要么第一段连续段的字符比第二段连续段的字符要大，称其为第二类限制。所以我们考虑对连续段进行 DP。对于连续段 \([l,r]\)，如果存在第一类限制的区间 \([L,R]\) 满足 \(l\le L\le i<R\)，那么后面接着的连续段的字符一定大于这个连续段。第二类限制同理。\(f(i,c,0/1/2)\) 表示考虑 \([1,i]\)，连续段结尾为 \(i\)，连续段字符为 \(c\)，且 \(i+1\) 开始的连续段的字符没有限制 / \(>c\) / \(<c\)。然后再令 \(g(i,c)\) 表示考虑考虑 \([1,i]\) 且 \(i+1\) 开始的字符为 \(c\) 的方案数。 \(f\) 相当于 \(g\) 的一个区间和，\(g\) 也可以由 \(f\) 求得。复杂度 \(O(26n+n\log n)\)。
https://qoj.ac/submission/106082
JOISC2022 Day2 复制粘贴 3 Copy and Paste 3
对于串 \(S\)，如果它的出现位置和一个长度大于它的串 \(T\) 相同，且不存在两个连在一起的 \(S\)，那么它就一定没用。于是需要的串的数量一共就 \(O(n)\)，暴力建后缀树然后看是否存在两个连在一起的出现次数即可。然后对于两个关键串 \(i,j\)，我们令 \(c_{i,j}\) 表示串 \(j\) 在串 \(i\) 中的不重叠的出现次数。令 \(l_i\) 表示 \(i\) 的长度，那么求一次 \(c_{i,j}\) 是 \(O(\frac{l_i}{l_j})\) 复杂度的，于是总共复杂度 \(O(n^2\log n)\)。然后就可以 \(O(n^2)\) 地进行 DP 了，每次枚举上一次 copy 的串即可。
https://qoj.ac/submission/106110
* JOISC2022 Day1 京都观光 Sightseeing in Kyoto
首先需要发现一件事情：有用的 \(a_i\) 一定在下凸壳上，\(b_i\) 同理。凸性的证明可以考虑调整法：对于 \(a_{i,j,k}\) 与 \(b_{x,y}\)，要从 \((i,x)\to(k,y)\)，发现 \((i,x)\to (j,x)\to (j,y)\to (k,y)\) 会更优当且仅当 \(a_i,a_j,a_k\) 是凸的。
然后我们相当于就是要把两个凸壳并起来，然后最优化一些东西。容易联想到凸壳的闵可夫斯基和。于是我们就按照斜率把它们给归并起来，归并的同时计算答案。
https://qoj.ac/submission/106204
JOISC2022 Day2 团队竞技 Team Contest
考虑直接贪心。我们维护三个堆，堆中分别按 \(x,y,z\) 排序，每次取堆顶。如果存在一个堆顶的元素不符合要求，那么我们发现这个无论怎样都不可能合法了，直接删掉即可。实际操作用 sort 后的数组维护即可。
https://qoj.ac/submission/106292
* JOISC2022 Day3 洒水器 Sprinkler
先是搞了一个 \(O(Qd\log n)\) 的不能通过的做法…然后发现可以分块+猫树变成 \(O(Q\sqrt n+Qd)\)…但是这代码得有 4kb…
实际上有更为简单的办法。考虑维护一些 tag，\(g_{u,d}\) 表示 \(u\) 子树中距离 \(u\) 为 \(d\) 的点的 tag。考虑如下的修改方式：对于 \(u\) 的 \(h\) 阶祖先 \(x\)，在 \(g_{u,d-h}\) 和 \(g_{u,d-h-1}\) 处打 tag。这样所有点都会被覆盖到。
https://qoj.ac/submission/106339
* JOISC2022 Day3 蚂蚁与方糖 Ants and Sugar
考虑将二分图最小匹配转化为最大独立集。用 X 表示蟻，O 表示糖，即选择尽量多的点，使得对于任意 X 与 O 之间的距离 \(>L\)。我们考虑 O 形成的一些区间。对于位于区间 \([x,y]\) 的一些 O，需要保证 \([x-L,y+L]\) 中没有 X。若令 \(S\) 表示 O 的前缀和，\(T\) 表示 X 的前缀和，那么我们先假定先选所有 X，那么区间 \((l,r]\) 的 O 的贡献就是 \(S_{r}-S_l-T_{r+L}+T_{l-L}\)。
令 \(x_i=-S_i+T_{i-L}\)，\(y_i=S_i-T_{i+L}\)，我们相当于就是需要交错地选择一些 \(x,y\)，最大化 \(\sum x+y\)。有了这个就可以维护矩阵了，\(f_{0/1,0/1}\) 表示区间中第一个选择的是 \(x/y\)，最后一个选择的是 \(x/y\)，是可合并的。但是注意到我们每次是一个后缀的修改，不是很好做。但是我们再仔细看一看修改的形式。若插入一个 O，那么就是后缀 \(x_i-a\)，\(y_i+a\)，这对一个状态的贡献只和 \(x/y\) 数量差有关，而数量差只会是 \(0/1\) 这个信息已经维护出来了，所以可以直接打 tag 修改。若插入一个 X，那么可以拆分成一个后缀 \(x_i+a\)，\(y_i-a\) 和一个区间 \(y_i-a\)。注意到这个区间是 \([x-L,x+L-1]\)，长度 \(\le 2L\)，所以只会有不超过 \(2\) 个 \(y\)（即最多只有一个整区间），所以可以再对于 \(\le 2L\) 的区间的状态记录 \(y\) 数量即可。
这个做法比较卡常，把转移手动循环展开了。然后把全 0 的给特判掉了。
https://qoj.ac/submission/106588
JOISC2022 Day4 一流团子师傅 Super Dango Maker
发现询问次数只有 \(nm\log m\)。考虑动态维护每个串 \(S_i\)，每次我们将目前的串加入编号最小的，可以加入的串，这样的话就保证了串的单调性，即 \(S_{i+1}\subseteq S_{i}\)，于是每次就可以二分。这个条件即对于所有 \(j<i\)，\(a_i\in S_j\)。也就是集合 \(S_i\cup\dots\cup S_m\cup \{a_{i+1},\dots,a_n\}\) 中，距离 \(m-i+1\) 个串恰好少一个 \(a_i\)。所以我们每次在二分时问这样的集合即可。
https://qoj.ac/submission/107628
* JOISC2022 Day4 鱼 2 Fish 2
* JOISC2022 Day4 复兴计划 Reconstruction Project
首先注意到每条边的贡献时间一定是一段区间 \([l,r]\)，又由于点数很少，所以可以暴力维护边的删和加。但是看上去很难直接维护得知哪些边要加哪些边要删，所以我们考虑不对时间扫，而对边扫。先建出最小生成树后，从小到大扫边，每次看这条边 \(i\) 形成的环上的最小边 \(j\)，并把它给替换了，并记录更改时间 \(r_j=l_i=\frac{w_i+w_j}{2}\)。复杂度 \(O(nm+(m+q)\log m)\)。
https://qoj.ac/submission/107902
标签：ac,https,submission,题解,JOISC2022,JOISC,2022,区间,qoj From： https://www.cnblogs.com/TetrisCandy/p/17422304.html