这个博客最近阅读量突然变得好多，甚至有同学开始 QQ 催更了（？）感觉非常受宠若惊啊。
实在找不到好题了，这篇博客里一半的题目都是从 1kri 老师的趣题里面牛过来的，如果大家有好题可以推给博主，非常感谢！！
84 12.23 考试 train
可以看出来是志愿者招募的模型，但是这样是不可做的。尝试找一些性质。
发现对于 \(t\geq 2\)，均可以构造出贡献为所有区间的并。所以单独处理 \(t=1\) 并动态维护 \(t\geq 2\) 即可。
85 12.23 考试 mex（利用单调性优化的 DS trick）
使用莫队可以给出 \(\mathcal{O}(n\sqrt{n})\) 的算法。
考虑另一个优化思路：从大到小枚举答案，并动态维护每个区间的判定信息，如果判定合法则删去区间。虽然较为难以维护，但是发现答案具有单调性：若存在包含关系，大区间的答案一定不小于小区间的答案。所以我们可以利用 QOJ2559 的技巧，只维护所有不被任何区间包含的区间，然后可以使用线段树快速维护判定信息。
86 12.23 考试 biology（线段树分治）
实际上可以泛化成动态图联通性问题，每次加入或删除 \(\mathcal{O}(1)\) 条边，并查询一个子矩形内的连通块数量。可以给出一个算法：对于一组询问，删除边界上的所有边，并查询矩形内的连通块数，可以使用树状数组维护连通块代表元，删边操作可以利用线段树分治来处理，复杂度大约是 \(\mathcal{O}(n^2+nq\log n)\)。
事实上可以基于欧拉公式 \(V-E+F=P+1\) 给出更好的算法。我们统计面的数量（此处相当于对偶图补图连通块数），而处理边界的时候，我们发现和外界联通的面不计入贡献，于是直接减去即可。复杂度为 \(\mathcal{O}(n^2+nq+q\log^2 n)\)。
87 qoj7943 LIS on Grid（Dilworth）
本来应该是 Solution Set 5 里面的题，由于一些原因需要再写一遍。
等价于构造 \(k\) 条反链，我们不妨假设第 \(i\) 条反链从 \((n-k+i,1)\) 开始，到 \((y,n)\) 结束。
考虑所有反链最多占据多少个格子，其为 \(k(m+n-k)\)，所以可以构造的条件是 \(k(m+n-k)\geq\sum a_i\)。
下面考虑构造，我们先令 \(a_i\gets\max(a_i,k)\)，然后逐步构造路径。如果 \(a_i>k\)，且上方格子为空，往上走，并令 \(a_i\gets a_i-1\)；否则往右走。
88 qoj7748 Karshilov's Matching Problem II
先 Z 一下，对于 \(i+z_i-1\leq r\) 的 \(i\) 是容易处理的，对于剩下的 \(i\)，找到最小的满足 \(i+z_i-1>r\) 的 \(i\)，发现 \([i,r]\) 为 \(T\) 的一段前缀，可以预处理前缀的答案。
所以串串还是要利用好相等的性质。
89 qoj7751 Palindrome Path（构造单位操作）
考虑往操作序列两端往内加入操作，并动态维护起点和终点额位置。关键在于构造操作，使得起点移动任意方向的一格，而终点位置不变。下面给出构造：
- 假设方向为 \(d\)，其反方向为 \(\text{op}(d)\)。先走 \(k\) 步 \(\text{op}(k)\) 使得一方不能走。
- 如果终点能走，则加入 \(\text{op}(d)\) 并加入 \(k\) 个 \(d\)。
- 否则，加入 \(k+1\) 个 \(d\)，因为终点还原的前驱可能是它本身。
搜出 DFS 树之后按上述规则构造可遍历所有结点。
90 qoj7620 Yet Another Subsequence Problem
万欧。
91 qoj7742 Suffix Structure（Trie 树上 LCP）
问题的难点在于：对于 Trie 树和给定串 \(T\)，求出每个结点子树内的所有串与 \(T\) 的 LCP。
给出如下算法：
- 按照 DFS 序遍历每个结点，维护 \(mat_u\) 表示 \(s_u\) 的最长后缀，使其是 \(T\) 的前缀。
- 暴力跳 Border，并考虑其在 \(T\) 的下一个字符 \(c\)。
- 若 Trie 上 \(u\) 有出边 \(c\)，则更新 \(mat_{\text{son}_{u,c}}\)，然后跳过 \(mat_u\) 的 Border 的一段后继相同的连续段。
- 否则，更新当前串起点位置的答案。
对于第一步，可以利用 Border / 周期等差数列性质证明跳跃次数不超过 \(\mathcal{O}(\log n)\)，对于第二步，每个点只会被更新一次，总复杂度为 \(\mathcal{O}(n)\)。
92 CF1896F Bracket Xoring（构造单位操作）
给出几组“单位构造”：
- \(s=\texttt{(()()()}\cdots\texttt{()())}\)，其会翻转 \(s_1\) 和 \(s_{2n}\)。
- \(t_i=\text{swap}(s,i)\)，表示交换 \(s\) 中 \(i\) 和 \(i+1\) 形成的串，其会翻转 \(s_1,s_i,s_{i+1},s_{2n}\)。
基于此可以给出 \(2n\) 的构造。而注意到奇数和偶数的 \(n\) 次构造可以压到一起，处理一下 \(s_1,s_{2n}\) 的问题可以做到 \(3\) 次。
Submission #238323535 - Codeforces
93 CF1909G Pumping Lemma
先求出 \(s\) 和 \(t\) 的最长公共后缀的长度 \(l\)，那么对于 \(s[1,n-l]\)，它一定只能作为串 \(x\) 中的一部分，于是可以把它和 \(t\) 中的一段前缀匹配之后删掉。
此时 \(s\) 是 \(t\) 的一段后缀。考虑 \(y\) 在 \(s\) 和 \(t\) 的出现位置：
- \(s=x+y+z\)。
- \(t=x+y^k+z\)。
由于 \(s\) 是 \(t\) 的后缀，所以串 \(x=y'y^i\)，其中 \(y'\) 是 \(y\) 的一段后缀。从另一个方面讲，串 \(x+y^k\) 具有周期 \(|y|\)。
于是可以用 [NOIP2020] 字符串匹配 的技巧，枚举 \(|y|\)（\((m-n)\bmod |y|=0\)），然后考虑 \(t\) 的后缀 \(t[|y|+1,n]\) 和 \(t\) 的 LCP，设为 \(l\)，那么 \(t[1,l+|y|]\) 是一个具有周期 \(|y|\) 的串，\(x+y^k\) 必然是它的一个前缀。考虑 \(|x|\) 的取值范围，需要满足 \(|x|+|y^k|\leq l+|y|\)，由于 \(|y^k|=|y|+m-n\)，所以合法的 \(|x|\) 的个数可以很快求出来。
可以使用 Z 函数处理 LCP，复杂度 \(\mathcal{O}(n)\)。
Submission #238798966 - Codeforces
94 loj3695. 「JOISC 2022 Day4」鱼 2（线段树）
定义不合法的段为 \(\min(a_l,a_r)>\sum _{i=l+1}^{r-1} a_i\) 的段，注意到包含一个点的不合法的段最多只有 \(\log V\) 个，考虑用线段树维护这些段。具体地，维护包含左端点的这 \(\log V\) 个段，包含右端点的这 \(\log V\) 个段，线段树尝试合并左儿子贴右端点的集合和右儿子贴左端点的集合，对于左儿子贴右端点的集合，尝试往右边扩展，如果能够扩展到右边端点，则把它加入新的右端点集合，可以用双指针维护。扩展的同时维护一段有多少个初始下标可以扩展到当前段。复杂度 \(\mathcal{O}(n\log n\log V)\)。
还有个 1kri 老师的做法：直接大力维护所有集合，然后找到不合法的区间做区间覆盖，区间覆盖用每个结点上的主席树维护，上传的时候把当前结点对应的主席树的左儿子设为左儿子的主席树，右儿子同理，然后在上面做区间覆盖。
提交记录 #1969192 - LibreOJ (loj.ac)
95 AGC028F Reachable Cells（容斥）
考虑求 \(val_{i,j}\) 表示 \((i,j)\) 能到达的数的和。先从 \(val_{i+1,j}\) 和 \(val_{i,j+1}\) 转移过来，然后容斥掉两个都能到的结点。
观察一下两个都能到的点的性质。可以发现：
- 如果 \((x_1,y_1)\) 和 \((x_2,y_2)\) 都能到并且 \(x_1<y_1\land x_2>y_2\)，那么一定存在一个非 \((i,j)\) 的点使得两个都能到。
证明画画就行。所以点的形态是：一个左上-右下点列和它们能到达的点。
预处理 \(g_{i+1,j,k}\) 和 \(f_{i,j+1,k}\) 表示到第 \(k\) 行两个格子能到达的最大位置和最小位置，可以找到第一个点。然后往下跳，下一个位置一定大于 \(h_{x,y}\) 及 \(x,y\) 能到达的行最大的点。复杂度 \(\mathcal{O}(n^3)\)。
Submission #48971569 - AtCoder Grand Contest 028
96 loj2336. 「JOI 2017 Final」绳
打表找规律可以发现合法的条件为删去第一段和最后一段之后剩下的每一段长度都是偶数。
然后枚举开头的奇偶性之后随便贪一下。
提交记录 #1969338 - LibreOJ (loj.ac)
97 loj578. 「LibreOJ NOI Round 2」小球进洞
刻画一个洞会装哪个球。设 \(cnt_i\) 表示位置在 \([1,i]\) 的球的个数，那么一定是 \(\min\{j|cnt_j-cnt_{i-1}\geq j-i+1\}\)。
移项之后发现 \(\sum b_i\) 就是求一段后缀最大值的下标和，\(\sum a_i\) 也是类似的刻画方法。楼房重建一下。
提交记录 #1969646 - LibreOJ (loj.ac)
98 loj3614. 「PA 2021」Desant 2（网格图最短路）
相当于 \(i\to i+1\) 连边，\(i\to i+k\) 连边，多次询问两点之间最短路。
可以把它弄成网格图的形式，其中原来的 \(i\) 是网格图上的 \((i/k,i\bmod k)\)。
然后你旅行者一下。
提交记录 #1969765 - LibreOJ (loj.ac)
99 loj3615. 「PA 2021」Fiolki 2（LGV 引理）
LGV 一下，给边赋上一个随机权值，视 \(f_i\) 为长度为 \(k\) 的向量，表示从 \(k\) 个起始点出发到 \(i\) 的路径条数，则 \(f(l,r)\) 为向量 \(f_{l\sim r}\) 的最大线性无关子集，也就是线性基的大小。时间戳线性基即可。
提交记录 #1969842 - LibreOJ (loj.ac)
100 loj3607. 「PA 2021」Wystawa（最大子段和，贪心）
有个比较套路的 set 维护凸包做法，感觉有点麻烦。下面是 1kri 老师做法。
先钦定全部选 A，然后把一些 \(a_i\geq b_i\) 的数往下调（不能调到 \(k\) 就交换 \(a_i,b_i\)）。二分，考虑如下贪心：每次加入一个数，如果当前最大子段和大于答案就贪心选对最大子段和影响最大的数往下调，感受一下。那么相当于求这样一个式子：设 \(c_i\) 表示 \(i\) 到当前位置的子段和，\(d_i\) 表示 \(i\) 还能往下调的量，那么：
前一项不太单调，但是其实把 \(d_k\) 换成 \(\max_{j=k}^i d_k\) 也是可以的。然后线段树二分即可。
提交记录 #1970064 - LibreOJ (loj.ac)
101 uoj177. 新年的腮雷（贪心）
二分然后倒着做。
考虑编一个贪心，从大往小考虑，如果最大值裂开之后仍然比当前序列中最大值大，那么一定要裂开。否则最大值一定要找一个数匹配，找到比最大值大的最小的即可。
提交记录 #671048 - Universal Online Judge (uoj.ac)
102 P8950 [YsOI2022] 道路修建（最小树形图）
把求最小树形图的算法中缩点的过程建树，那么问题转化成一个 \(k\) 个点链并大小的期望。
记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
我左偏树没 pushdown 过了模板。。。
103 ARC156E Non-Adjacent Matching（匹配模型）
如果不考虑相邻不能匹配的限制就是没有绝对众数。考虑的话稍微修一下就知道是 \(2(x_i+x_{i+1})\leq S\)，必要性显然，构造考虑把所有数拆成 \(1\) 排成一排，然后 \(i\) 和 \(i+\frac{S}{2}\) 匹配。
然后考虑计数，计数考虑容斥一下，可以发现只有可能是一个或者两个挨在一起，然后 DP 一下。
Submission #49003466 - AtCoder Regular Contest 156
我以为不能有重边，然后不会做没有限制的情况，后来发现这东西叫 Erdos-Gallai 定理。相信 OIer 能够猜出来这个定理
104 AGC056B Range Argmax（双射计数）
切入点比较难找。
考虑一个求 \(x\) 的算法：找到 \(p_i=n\) 的位置，以及所有跨过它的线段，把这些线段解决之后扔掉，递归两边做。
考虑造一个双射，即上述求 \(x\) 的算法和 \(x\) 之间的双射，这样我们就可以计数 \(p\) 生成 \(x\) 的过程来计数 \(x\)。那么我们钦定每次找到的位置都是最小的，也就是说，不存在更小的位置使得能够生成相同的 \(x\)。那么右侧没有限制，左侧需要保证下一个断点必须和当前断点被至少一个区间同时包含。可以设 \(f_{i,j,p}\) 表示区间 \([i,j]\) 且断点 \(\geq p\) 的方案数，容易 DP。
Submission #49004050 - AtCoder Grand Contest 056
一般的计数都是构造判断合法的算法然后 DP 判断。这个题通过构造生成对象的方式，将生成过程之间与对象本身建立了双射，从而我们可以计数新的对象。
好绕。。。
105 2024.1.4 考试 game（一个子序列划分计数模型）
可以确定的是：\(a\) 是单谷的。那么在 \(k\) 之前，\(b\) 可以被拆成两个递减序列，\(k\) 之后，\(b\) 可以被拆成一个递增序列和一个递减序列，且递增序列的末尾小于递减序列的末尾，且后面的最大值小于前面的其中一个序列的最小值。
考虑 \(k=n\)，可以 DP 解决：注意到限制形如没有 123 形式，在状态中记录 2 的最小值 \(j\)。那么 \(f_{i,j}\) 可以插一个最小值转移到 \(f_{i+1,j+1}\)，也可以插一个 \(k\leq j\) 转移到 \(f_{i+1,k}\)。这是格路计数模型，容易线性解决。
考虑 \(k=1\)，答案是 \(2^{n-2}\)。
考虑拼起来，那么后面的最大值要小于 \(f_{k-1,i}\) 的 \(i\)，先给后面分配数，发现这就是插板。枚举一下 \(i\) 即可。
106 2024.1.4 考试 function
考虑res的部分。刻画一个数在第 \(i\) 轮的值，发现它就是前缀第 \(i\) 大和它取 \(\min\)，那么它的贡献就是它变小的次数也就是前缀本质不同的比它小的数。
考虑vs的部分，注意到操作是平移前缀最大值，且 \(i\) 加入前缀最大值的时间可以确定：计算 \(i\) 前面比 \(i\) 大的数的个数。于是找到第一个和 \(a_i\) 不同的前缀最大值位置，执行后缀加即可。
107 2024.1.4 考试 knight
如果两个向量不平行可以解个方程转化成有禁止位置的格路计数问题，容斥一下。
否则是数轴上的问题，找 \(10^6\) 个点暴力 BFS 即可。
108 AGC007E Shik and Travel
考虑暴力：二分，然后找到子树内所有加入-删除点对 \((u,v)\)，每次合并 \(v_1+u_2\leq X\) 的点对。
把二维偏序的点对去掉，那么轻子树每个点作为开头 / 结尾的点都是唯一的。所以暴力这些点对即可，复杂度 \(\mathcal{O}(n\log^2 n)\)。
Submission #49015878 - AtCoder Grand Contest 007
109 AGC010E Rearranging（贪心，充要条件）
考虑从前往后贪心。
先考虑第一个数的最小值。注意到，如果我们把 \(x\) 设为最小值，那么会给 \(x+1\sim n\) 设立限制，即在它们之前必然存在一个和它不互质的数。我们把这些数称为被固定的。
在这个限制下，考虑合法的充要条件：将不互质的数建图，每个联通块都存在一个未被固定的点。构造如下：每次选出最大的未被固定的点，将其填入，其相邻点都变为固定。如此操作，一定能找到方案。
从大往小尝试，找到能填的最小的，然后将比它大与它没有连边的数标记为固定，与它相邻的点标记为未固定。我们需要得到联通块信息，而图较为稠密，可以使用 bitset 优化遍历。复杂度 \(\mathcal{O}(n^2\log V+\frac{n^3}{w})\)。
Submission #49023494 - AtCoder Grand Contest 010
110 loj4008「USACO 2023.12 Platinum」Cowntact Tracing
从子树往上贪心，策略是选择尽可能高的结点。
假设有解，考虑判断一个子树里面是否还要加新结点，也就是仅凭子树外的点能否覆盖掉所有结点。设 \(closest_u\) 表示离 \(u\) 最近的可以在第 \(0\) 天被感染的结点，如果 \(closest_{par_u}\) 覆盖不了 \(u\) 子树内最深的结点就把 \(closest_u\) 加进答案里面。
复杂度是线性的。存在一些巨大长剖线性对数做法，我没写出来/tuu
111 loj4009「USACO 2023.12 Platinum」A Graph Problem
题意是快速模拟 Prim 算法。可以发现边集一定是 MST，所以把 MST 求出来可以把问题转化到树上。
考虑从小到大枚举边，设 \(f_{u,i}\) 表示 \(u\) 在只考虑 \(id\leq i\) 的边的情况下的答案。此时加入 \(i+1\)，假设两端点分别为 \(u_{i+1},v_{i+1}\)，那么对于 \(u_{i+1}\) 所在的联通块，所有结点的答案末尾都要加上 \(f_{v_{i+1},i}\)。
考虑快速维护这个过程，发现每次修改都是重构树上一个子树，所以可以用线段树维护 \(f\) 值，操作相当于区间乘法、区间加、单点查。
112 loj4010「USACO 2023.12 Platinum」Train Scheduling
问题相当于要把数轴划分成两种颜色的段，使得每段长度 \(\geq T\)，权值是每辆列车后面与它颜色相同的第一段的开头时间的和。
一个直观的想法是设 \(f_{i,j}\) 表示覆盖了 A 集合的前 \(i\) 个和 B 集合的前 \(j\) 个，然而这样实际上是要记录时间信息的， 因为最后一辆列车未必在 \(t_i\) 时刻发车。
注意到如果我们找到这些列车，后面会构成子问题。考虑在两个准时列车 \(x,y\) 之间应该如何安排，发现其中每一段都应该是长度恰好为 \(T\) 的段，因为中间的列车没有一个准时的，在这个前提下无论怎么调整解都会变劣。
可以想到一个 DP：设 \(f_i\) 表示 \(i\) 为当前最后一个准时列车，最小的代价。转移考虑找到下一辆准时列车，并计算中间的贡献，贡献是容易计算的。问题在于，中间可能仍然有一些列车没有找到下一段的开头，假设最近的开头是 \(t_j+T\)，那么 \([i,j]\) 一整段的列车都是准时的。我们设 \(g_{i,c}\) 表示有 \(c\) 辆列车没有计算贡献，且 \(i\) 准时的答案。由于列车准时，转移较为平凡。
113 loj3032. 「JOISC 2019 Day1」馕
你肯定会 \(n=2\)。
你肯定会。
提交记录 #1971700 - LibreOJ (loj.ac)
114 loj3039. 「JOISC 2019 Day4」蛋糕拼接 3
它不凸，因为下凸函数取 \(\max\) 就不凸了。
但是它有决策单调性，所以写个分治，用类似莫队的方法维护一下堆，就好了。复杂度 \(\mathcal{O}(n\log^2 n)\)。
提交记录 #1971817 - LibreOJ (loj.ac)
感觉不如树状数组维护。
115 loj3914. 「PA 2022」Płótno（平面图连通性）
欧拉公式 \(V-E+F=P+1\)，所以可以线段树大力维护一下 \(V,E,F\)。
一般的情况 \(F\) 只会是四个点，但是这里可能是一个环。如果你比较笨实际上是可以用一些分治技巧把环找出来的。但是实际上没必要，因为有环联通块数一定是 \(1\)，所以 \(V-E+F=2\)，而我们求的 \(F'=F-1\)，所以把 \(P'\) 和 \(1\) 取 \(\max\) 即可。
我比较笨。
提交记录 #1972026 - LibreOJ (loj.ac)
1kri 老师给了一个更有启发意义的做法：因为问题是数联通块，所以可以找代表元，钦定代表元是位置最小的节点即可。
116 loj3225. 「PA 2019」Podatki drogowe
常规的做法是二分值，但是值比较大，所以可以考虑二分路径。
具体地，每次随机一条在当前范围内的路径，然后判断有多少个路径权值小于它。
但是随机在范围内的路径比较困难。边分治转化问题，把边按照权值排序之后，每个左链对应的是在一个区间内的右链，所以只需要记录区间范围。实现的时候可以把边分治离线下来。
然后问题是怎么判断两条路径的大小关系。我们可以在边分治的时候记录一个主席树，查询的时候直接对四个根在主席树上二分。
可以设置二分次数为 \(50\) 次。
提交记录 #1972528 - LibreOJ (loj.ac)
117 loj3217. 「PA 2019」Desant
考虑一个暴力 DP：设 \(f_{i,S}\) 表示前 \(i\) 个选了 \(S\) 集合的答案。
考虑压一压状态。注意到对于一个前缀的值域连续段（即中间不可能插数），我们只关心它有多少个数，而不关心具体选了什么。所以可以把状态合并。
毛估估一下是可以得到 \(\mathcal{O}(3^{\frac{n}{3}})\) 的上界的，实际可能更小。