JOISC2020 Day1 建筑装饰4 Building4
我们发现 \(A\) 的个数是连续的，所以我们只需要 DP 出最大的 \(A\) 的个数和最大的 \(B\) 的个数，若两者都 \(\ge n\) 那么就有解。然后再从后往前推出方案即可。
https://qoj.ac/submission/109314
* JOISC2020 Day1 汉堡肉 Hamburg Steak
我们有一些边界，最小的 \(r\)，最大的 \(l\)，最小的 \(u\)，最大的 \(d\)，那么我们一定可以用一种方法，使得每一个边界都被覆盖到。对于 \(K\le 3\)，则必然存在一个点位于两个边界的交点处，于是可以直接暴力枚举，复杂度 \(O(4^kN)\)。
现在考虑 \(K=4\) 如何做。上面的方法不再适用，但是我们可以考虑每个边界上选择的点的位置。先把这四个边界围成一个大矩形。对于一个矩形，若它和大矩形的交点数量 \(>2\)，那么可以发现它无论怎样都会被覆盖到。若数量 \(=1\)，那么相当于就是限定一条边上的选点的位置位于一个区间。若 \(=2\)，那么就是限定两条边中至少有一条边，上面的点位于某个区间内。这个限制可以用前缀优化建图的方式。由于离散化复杂度 \(O(n\log n)\)。
https://qoj.ac/submission/110040
* JOISC2020 Day1 扫除 Sweeping
考虑没有插入点的情况：每个操作都可以变成这样的形式，举往右扫为例：\(x\in[p_l,n-l]\)，\(y\in [0,l]\)，\(x\leftarrow n-l\)。这个 \(p\) 是往上扫覆盖到的最大的 \(l+1\)。于是考虑动态维护向右扫需要用的 \(p_i\)，以及向上扫需要用的 \(q_i\)，每次横着扫会对 \([p_l+1,n-l-1]\) 的 \(q\) 进行对 \(l+1\) checkmax 的影响。求出这些 \(p,q\) 后这些操作就分开了，横竖扫各不影响。对于一批向右扫的操作，我们对它进行排序，然后把这些询问也排序后一起处理。
考虑有插入点的情况：每个问询相当于可以变成，对于初始 \((x,y)\)，经历了一个区间的操作后，会变成什么坐标。考虑线段树分治，线段树每个节点都暴力处理出真实问询，把挂在上面的节点给处理掉。复杂度两只 log。
https://qoj.ac/submission/109633
* JOISC2020 Day2 变色龙之恋 Chameleon's Love
对于 \(i,j\)，若 \(\{i,j\}\) 的答案为 \(1\)，那么要么它们是单相思关系，要么是同色。考虑把这两种关系一起建边。那么一个点的出度为 \(1\) 或 \(3\)，如果是 \(1\) 那么必然为同色，如果是 \(3\) 那么必然有两个单向关系，可以通过 \(2\) 次问询确定 \(u\) 喜欢的对象，然后所有单向确定了就可以确定其它所有的同色关系了。
如果原图是二分图那么是简单的，可以直接对另一边的集合二分。但是现在并不是如此，但是实际上我们考虑从小往大考虑，每次我们其实需要只考虑前 \(i-1\) 个点形成的二分图关系就可以问出 \(i\) 和 \([1,i-1]\) 的边了。然后就结束了。
https://qoj.ac/submission/110133
JOISC2020 Day2 有趣的 Joitter 交友 Making Friend on Joitter is Fun
对于互相关注的两个点，我们把它合并起来，最终形成一些块，令 \(F_x\) 表示块 \(x\) 的前驱的点集合，\(S_x\) 表示块 \(x\) 的点集合那么答案就是块内任意连边的边数，加上 \(\sum |F_x||S_x|\)。我们每次按 \(|S_x|\) 合并，根据启发式合并的那一套理论，无论什么集合只要遍历更新 \(|S_x|\) 小的那个复杂度就是对的，所以 \(F_x\) 也可以直接合并。但是现在问题是我们要判断两个块之间有没有边，所以还需要维护 \(G_x\) 表示块 \(x\) 的前驱块集合，\(H_x\) 表示块 \(x\) 的后继块集合，这两个也是好合并的。最后一个问题是可能合并 \(x,y\) 时会有一些新的可合并的集合对，具体而言，满足 \(z\in H_x\cap G_y\) 或 \(z\in G_x\cap H_y\) 的 \((z,x)\) 也应该被合并。所以每次暴力找 \(z\)，然后加入更新队列即可。复杂度不会严谨证明，但是就是对的，\(O(n\log^2 n)\)。
https://qoj.ac/submission/109344
* JOISC2020 Day2 遗迹 Ruins 3
考虑改变题目描述的过程，从按值域从大到小变成从后往前考虑。那么我们相当于每次维护一个 bool 数组，然后每次找到 \(\le h_i\) 的最小的零位置 \(p\)，将数组的 \(p\) 位置设为一。但是实际上，影响一个柱子最后是否存活只依赖于这个 bool 数组的极长前缀一的长度。考虑进行 DP，\(f_{i,j}\) 表示对于后缀 \([i,2n]\)，数组的极长前缀一的长度为 \(j\)。令 \(c_i\) 表示 \([i+1,2n]\) 的没存活的个数，\(d_i\) 表示存活的个数。
考虑转移。如果这个位置最终没有存活，那么只能填 \([1,j]\) 中的数。但是这 \(2j\) 个数中一定有 \(j+c_i\) 个数已经被用掉了。剩下的数中有的数是重复出现的，我们不想处理这些东西，于是就考虑把每个数的两次出现区分开来，最后再乘上 \(2^{-n}\) 即可。所以没有存活的转移就是 \(f_{i,j}=f_{i+1,j}\times (j-c_i)\)。然后如果这个位置最终存活了，如果连续段没有变长就直接 \(f_{i+1,j}\)，把这个贡献交给之后统计。
如果变长成为了 \(j'\)，那么我们首先考虑第 \(i\) 个位置能填 \([j+1,j']\) 的数，且这些数一定有 \(j'-j-1\) 个数已经被用了，所以有 \(j'-j+1\) 种填法。然后我们从剩下的还没填的 \(d_i-j\) 个位置中选出 \(j'-j-1\) 个数，让这些数形成长度为 \(j'-j-1\) 的连通块。考虑设这个为 \(g_{i,j}\) 表示 \(i\) 个位置填出 \(j\) 个数的连续段，这个需要每时每刻保证 \(i\ge j\)，转移枚举 \(j\) 填了几个即可。复杂度 \(O(n^3)\)。
https://qoj.ac/submission/110098
JOISC2020 Day3 星座 3 Constellation 3
把整张图反过来，\(a_i=n-a_i+1\)，\(y=y-n+1\) 这样，那么我们就每次找到区间 \(a_i\) 最小的地方，于是区间中 \(\le a_i\) 的只能有一颗星星。递归左右部分，然后假设左边保留的星的纵坐标 \(\ge a_i\) 的最大总和为 \(S_l\)，右边的为 \(S_r\)，那么就用左侧的 DP 值 \(+S_r\) ，和右侧的 DP 值 \(+S_l\)，以及选择第 \(i\) 列上的星星 \(+S_l+S_r\) 来更新。线段树合并就可以维护了。
https://qoj.ac/submission/109499
JOISC2020 Day3 收获 Harvest
考虑人不懂，苹果动。令第 \(i\) 个人逆时针走 \(C\) 后遇到的人为 \(to_i\)，那么苹果一定是走到后面的一个人然后不断跳 \(to_i\)。\(to\) 会形成一个基环树，于是树上的点就可以用线段树合并来处理。然后处理环，令人 \(i\) 在环上的位置为 \(x_i\)，环上边权和为 \(L\)。然后对于苹果 \(i\)，令它第一个走到的环上点为 \(u_i\)，时间为 \(t_i\)，那么问询 \((v,T)\) 的答案为 \(\sum_j [t_j\le T](\lfloor\frac{T-x_v-t_i+x_i}{L}\rfloor+[x_v\le x_{u_i}])\)。把这个下取整拆开，拆成两个下取整相加，加上一个关于模 \(L\) 余数的二维数点，就可以单 log 做完了。代码较为复杂。
https://qoj.ac/submission/109571
JOISC2020 Day4 首都城市 Capital City
考虑点分治，每次考虑分治连通块内的，经过分治中心的首都长什么样。如果遇到了需要跑到连通块外的颜色，那么就直接不合法。否则直接暴力进行 BFS，于是每个点在一次分治中只会被访问一次，复杂度 \(O(n\log n)\)。
https://qoj.ac/submission/109728
JOISC2020 Day4 治疗计划 Treatment Plan
考虑做如下的转化：对于计划 \(i,j\) 满足 \(t_i\le t_j\)， 若 \(r_i-(t_j-t_i)\ge l_j-1\)，那么连边 \(i\to j\)；同样的，若 \(l_i+(t_j-t_i)\le r_j+1\)，那么连边 \(j\to i\)。然后 \(l=1\) 的和源相连，\(r=n\) 的和汇相连，那么我们就转化成了一个最短路的模型。然后上述的条件都可以用主席树优化建图，然后再 dijkstra 最短路。
下面分析一下复杂度。首先考虑本题只有点有点权，而这样的图跑 dijkstra 复杂度是 \(O(|V|\log |V|+|E|)\) 的，因为一个点只会被松弛一次。其次，注意到实际上我们只有 \(n\) 个点，即代表原区间的点是有点权的，其他点都是零权的。对于零权的点，我们开一个 queue 维护目前松弛到的零权点，一个堆维护有权点，每次清空 queue 之后再看堆中的点，复杂度就变成了 \(O(n\log n)\)。