1656
F. Parametric MST
给出 \(a_1,a_2,...,a_n\)。定义 \(G(x)\) 是这样一张完全图：对于任意两点 \(i\neq j\)，定义其边权为 \(w(i,j)=a_ia_j+x(a_i+a_j)\)。（以下的 \(x\) 都是指实数）。
定义 \(f(x)\) 为 \(G(x)\) 的最小生成树权值。求 \(f(x)\) 的最大值，或输出 INF 表示 \(f(x)\) 可以取到无穷大。
\(n\le 2\times 10^5,|a_i|\le 10^6\)。
解决这类题。还是有一定套路可循的。首先我们应该研究 \(x\) 固定的时候最小生成树的构造方式，它应当足够简单，否则我们怎么能寻找 \(f(x)\) 的最大值。
考虑研究边权，固定 \(i\)，那么 \(a_ia_j+xa_i+xa_j\) 中就只剩下了 \(a_ia_j+xa_j=a_j(a_i+x)\) 待定。此时显然，如果 \(a_i+x\le 0\)，我们会考虑让它和 \(a\) 最大的连，这样边权是最小的；反之，如哦 \(a_i+x\ge 0\)，它和 \(a\) 最小的连，边权是最小的。
如果这样连，最后确实能构成一棵树，那显然就是 mst。
方便起见，可以把 \(a\) 排序。那么 \(a\) 的一段前缀和 \(a_n\) 连边是最优的，剩余部分（形成一个后缀）和 \(a_1\) 连边是最优的。当前缀长度 \(=0\) 或者 \(=n\) 的时候，显然就是所有边和 \(a_1\) 或者 \(a_n\) 连（除了自己不和自己连），那显然构成的是一颗树。如果前缀长度不是 \(0\) 也不是 \(n\)。那么实质上 \(a_1\) 和 \(a_n\) 的连边会被算两次，把这条边的权值去掉一遍即可。
到这里我们发现 \(f(x)\) 其实可以看成一个一次函数，这个一次函数的解析式只会变化 \(n+1\) 次。每次的 \(x\) 都有一个取值范围 \([L,R]\)，然后问 \(f(x)\) 的最大值。此时一切都变得很简单了。
时间复杂度 \(O(n\log n)\)，瓶颈在排序。
1679
E. Typical Party in Dorm
定义 \(f(S)\) 为字符串 \(S\) 的回文子串数量。
给出一个字符串 \(S\)，有些位置已经确定，剩下位置是问号。有 \(q\) 次询问，每次询问给出一个字符集 \(T\)，求：
把 \(S\) 中每个问号位置填入一个 \(T\) 中的字符，问 \(\sum f(S)\) 模 \(998244353\) 的值。
\(S\) 和 \(T\) 的字符集都是 \(\in \{a,b,c,...,q\}\)（前 \(17\) 个小写英文字母）的。\(|S|\le 1000,q\le 10^5\)。
注意到 \(|S|\le 1000\) 的限制。所以我们可以暴力枚举 \(|S|\) 的每一个子串，然后计算它对答案的贡献。
那么有两种位置，中心和两侧（也可能没有中心位置）。对于两侧，即位置 \(x-y\) 建立了一个对应。如果 \(x-y\) 中只有一个问号，则这个问号的位置填的值是确定的，我们记作 \(c\)，这样本质自由的问号数减一。
记 \(A=\cup c\)，则当且仅当给出的 \(T\) 满足 \(A\in T\) 的时候我们枚举的这个子串才会对 \(T\) 造成贡献。然后记本质自由问号个数为 \(num\) 则贡献为 \(|T|^{num}\)。
注意到 \(num\) 和 \(A\) 有关，但是 \(|T|\) 是和 \(T\) 有关的。所以我们无法直接用一次高维前缀和来计算全部答案。
但是注意到 \(|T|\) 只有 \(17\) 种取值，所以当我们加入一个本质自由问号个数为 \(num\) 的子串的时候，对于每个 \(1\le i\le 17\)，我们都把 \(f(i,A)\) 加上 \(i^{num}\)。然后对每个 \(f(i)\) 进行高维前缀和。最后 \(f(|T|,T)\) 就是所求。
时间复杂度 \(O(n|S|^2+n^22^n)\)，其中 \(n=17\)。注意略有卡常。
F. Formalism for Formalism
考虑所有 \(\le 10^n\) 的非负整数，位数不够则最高位补零。
给出 \(m\) 对关系 \((u_i,v_i)\)。对于一个数的相邻两位 \(u,v\)，如果 \((u,v)\) 或 \((v,u)\) 存在于给出的关系中，则我们可以交换它们。
若 \(A\) 可以通过若干次交换得到 \(B\) 则 \(A\) 和 \(B\) 本质相同。
问一共有多少个本质不同的数，模 \(998244353\)。\(n\le 5000,m\le 45\)。
感觉挺牛逼的题。
首先我们的想法是为每个等价类找一个代表去计数。容易想到字典序最小。换言之一个数被计数当且仅当不能通过交换让它的字典序变得更小。
那么一个直接的想法是从前往后地 \(dp\)。但是我们发现记录末尾，末几位的信息都无法保证这个约束。
事实上如果我们最高位放了个 \(c_1\)，那么第二位不能放 \(c_2\)，当且仅当 \((c_1,c_2)\) 可交换且 \(c_1\gt c_2\)。当我们放好 \(c_2\) 后，同理会禁止掉一些 \(c_3\)。此外，如果 \(c_3\) 和 \(c_2\) 可交换，那么就算 \(c_3\gt c_2\)，如果 \(c_3\) 被 \(c_1\) 禁止掉了，那 \(c_3\) 也不能填入第三位。
换言之如果我们知道当前哪些数字不能填到下一位。则填完下一位后，我们可以方便地计算哪些数字不能填到下下位的。
所以直接令 \(f(i,S)\) 表示前 \(i\) 位确定，第 \(i+1\) 位不能填 \(S\) 中的数。注意到本质不同的转移只有 \(2^{10}\times 10\) 种，对每种预处理一下就行。
时间复杂度 \(O(10\times 2^{10}\times n)\)。注意实现。
启示：当 dp 一步能填的状态很少的时候，可以直接记录每一步能填哪些状态来转移。
1682
E. Unordered Swaps
给出一个 \(n\) 排列 \(p\)，设其通过任意交换排序的最少步数是 \(m\)。接下来给出一个长度为 \(m\) 的二元组 \((x,y)\) 组成的序列 \(q\)。重排 \(q\) 使得按此时顺序交换 \(p_{x_i},p_{y_i}\) 后，\(p\) 是有序的。保证存在一组合法解。
\(2\le n\le 2\times 10^5,1\le m\le n-1\)。
可以vp场切 2700* 构造了，可喜可贺。
任意交换排序，是经典到不能再经典的问题了。显然 \(m=n-k\)，其中 \(k\) 是置换环数量。
如果一个排序步骤花费步数是最少的，则每步都在拆环。首先对初始的 \(p\) 找出所有的置换环，显然 \(q\) 中不会有一个 \((x,y)\) 是分属于两个置换环的。
容易发现不同置换环之间没有任何影响。所以我们考虑单个置换环上的构造。以下所有数对都属于一个置换环。
如果有两个数对 \((a,b),(c,d)\) ，四个数两两不同，则它们谁先执行是无所谓的，放在置换环上考虑，就是说弦 \(ab\) 与弦 \(cd\) 有交，此时是不合法的：因为你不管先执行哪一个，另外一个数对一定无法执行（因为两个数分属两个置换环）。
又显然 \((a,b)\) 不会出现多次，换言之我们只用考虑 \((a,b)\) 和 \((a,c)\) 这样的数对，哪个在前哪个在后。（类似地还要考虑 \((b,a),(c,a)\) 这样的对的顺序。）
稍微手玩后立马发现，设 \(f(x)\) 是置换环上 \(a\) 走到 \(x\) 的步数，则 \((a,b)\) 排在 \((a,c)\) 前当且仅当 \(f(b)\lt f(c)\)。
所以对于所有的 \((a,x)\) 我们按照 \(f(x)\) 排序即可。这样会构建出若干个先后的约束，连边后拓扑即可。拓扑序即为一组合法解。
至于如何求 \(f(x)\)，其实只要对一个置换环上的点按顺序编个号，然后 \(a\) 和环长确定了以后 \(f(x)\) 显然是好求的。
时间复杂度 \(O(n\log n)\)。
F. MCMF?
给出两个长度为 \(n\) 的序列 \(a,b\)，保证 \(b_i\neq 0\)。然后给出 \(q\) 次询问，每次给出一个区间 \([l_i,r_i]\) 且保证 \(\sum_{l_i\le k\le r_i}b_j=0\)。求下列图的最小费用最大流：
共 \(r_i-l_i+1\) 个点外带上源、汇 \(S,T\)。\(b_i\lt 0\) 的在左侧，对这样的点，\(S\rightarrow i\) 连一条容量为 \(|b_i|\) 费用为 \(0\) 的边；\(b_i\gt 0\) 的在右侧，对这样的点，\(i\rightarrow T\) 连一条容量为 \(|b_i|\) 费用为 \(0\) 的边。对于 \(b_i\lt 0,b_j\gt 0\)，\(i\rightarrow j\) 连一条容量为 \(\infty\) 费用为 \(|a_i-a_j|\) 的边。
\(n,q\le 10^5,|b_i|\le 10^9,0\le a_1\le a_2\le ... \le a_n\le 10^9\)。
应该是本月以来见到的最难的一道 DS 了。首先希望大家可以注意到 \(a\) 递增的限制，我眼瞎没看到这个限制浪费了一天思考时间。
问 \(q\) 次最小费用最大流这个东西看上去就很恐怖啊，我们把它转成些更可做的东西。套路地考虑只询问一次 \([1,n]\) 怎么做。
首先容易发现我们肯定是左右两边各自按照 \(a\) 排序去匹配的。然后题目里 \(a\) 已经排好序了所以实质上是按照出现顺序匹配。
这样一次询问可以 \(O(n)\) 做了，难以优化，因为绝对值难以处理。
研究一个位置 \((a_i,b_i)\) 的贡献，显然其一段前缀的贡献为 \(a_i\) 剩余后缀的贡献为 \(-(a_i)\)。而这个具体的数量其实只和前面还剩下多少个未匹配的点有关。不妨设 \(b_i\lt 0\)，则令 \(S=\sum_{k\lt i}b_k\)，当 \(S\le 0\) 时，总贡献为 \(-a_i|b_i|\)；当 \(0\lt S\le |b_i|\) 时，总贡献为 \(2Sa_i-a_i|b_i|\)；否则总贡献为 \(a_i|b_i|\)，\(b_i\gt 0\) 的情况有类似贡献。
另外我们设 \(suf_i\) 是 \(a[i...n]\) 匹配后的结果（不要求一定能匹配完），则显然对一次询问有 \(ans=suf_{l}-suf_{r+1}\)，因为你保证了区间的 \(\sum b=0\)，也就是说前面的对后面的匹配不造成任何影响。
所以问题变成了快速预处理 \(suf_{1\sim n}\)。
这个时候注意到对于一对 \(i\le j\)，\((a_j,b_j)\) 对 \(suf_i\) 的贡献只和 \(S_{j-1}-S_{i-1}\) 有关，根据上面对“贡献”的研究，实际上 \((a_j,b_j)\) 对 \(suf_i\) 的贡献是一个分段的函数，每一段都是关于 \(suf_i\) 的一个一次函数。所以开两颗线段树（树状数组）维护一次项系数和常数项即可。时间复杂度 \(O(n\log n)\)，注意要先离散化。
1684
F. Diverse Segments
给出一个长度为 \(n\) 的数组 \(a\)。定义 \(a\) 的一个子段 \([l,r]\) 是好的当且仅当 \(a_l\sim a_r\) 中元素两两不同。
现在给出 \(m\) 个子段 \([l_i,r_i]\)。你需要执行一次操作：选择 \(a\) 的一个区间，然后把这个区间的每个数分别替换成任意整数。要求操作完毕后给出的 \(m\) 个子段均是好的。
输出打到这个目标，操作区间的最短长度。如果不用操作，则输出 \(0\)。
\(n,m\le 2\times 10^5,a_i\le 10^9\)。
考虑把一个区间合法转成更可做的约束。设 \(pre_i\) 是上一个和 \(a_i\) 相同的位置（没有则 \(pre_i=-1\)），则实际上对于 \(i\in [l_j,r_j]\)，应该满足 \(pre_i\lt l_j\)。
从一个区间变成多个区间，我们发现，对于一个 \(i\)，只要设 \(lim_i\) 是所有包含 \(i\) 的区间中，\(l_j\) 最小的那个（没有则 \(lim_i=\infty\)），则实质上题目的约束是 \(\forall i,pre_i\lt lim_i\)。
\(pre\) 和 \(lim\) 的求解都是经典问题，不再赘述。
把一个数任意重赋值的过程可以看作将它的 \(pre\) 置为 \(-\infty\)，同时将 \(pre_{nxt_i}\) 置为 \(pre_i\)。
另外，设 \(f(l)\) 是最小的 \(r\) 使得删去 \([l,r]\) 合法（不存在这样的 \(r\) 则 \(f(l)=\infty\)）。显然 \(f(l)\) 单调不降。换言之可以考虑双指针。
所以我们需要处理动态地删除/加入一个位置，并维护是否满足所有位置 \(pre_i\lt lim_i\) 成立。
设一个计数器 \(cur\) 初始为 \(0\)。每当有一个 \(pre_i\ge lim_i\) 则 \(cur\) 增加 \(1\)。则实际上是动态维护 \(cur\)，合法等价于 \(cur=0\)。
离散化 \(a\) 后用 \(set\) 维护每个数的所有出现位置。就可以动态计算每个位置的 \(pre\) 和 \(nxt\)：因为你注意到删除/加入一个位置只会修改 \(O(1)\) 个位置的 \(pre\) 和 \(nxt\)。修改一个位置后重新计算其对 \(cur\) 的贡献即可。时间复杂度 \(O(n\log n)\)。
G. Euclid Guess
考虑欧几里得算法的过程：求两个正整数的 \(\gcd\) 并使用辗转相除的形式。本题中，有一个初始为空的数组 \(t\)，每一次求两个数的 \(\gcd\)，就把辗转相除过程中的所有非零余数加入 \(t\) 中。
现在给你一个长度为 \(n\) 的序列 \(p\)，你需要构造一个长度不超过 \(2\times 10^4\) 的数对构成的数列 \(a\)，满足：
-
每个数对的元素都是 \([1,m]\) 之间的正整数
-
对所有数对的两个数分别求 \(\gcd\) 后得到的序列 \(t\) 可以通过任意排序和 \(p\) 完全相同。
无解输出 \(-1\)。\(n\le 10^3,1\le m\le 10^9\)。
我第一次独立杀了 2800* 的构造啊，这个题非常值得一做的还是。
第一 \(2\times 10^4\) 是诈骗，加一个数对肯定至少让 \(t\) 的长度增加 \(1\)，否则加了没用。所以你的答案长度肯定 \(\le n\)。
然后考虑无解。事实上如果想要有一步余数为 \(a\)，那么最小的数对是 \((2a+1,a+1)\) 这样第一步余数得到 \(a\)。换言之如果 \(p\) 中有一个元素 \(x\) 使得 \(2x+1\gt m\) 则无解。
换言之，\(p\) 中每个元素 \(\lt \left\lceil \frac{m}{2} \right\rceil\)。
然后考虑对于某些元素 \(x\)，你可以直接放一个 \((3x,2x)\) 进去。这样的 \(x\le \left\lfloor \frac{m}{3} \right\rfloor\)。这样这个过程中只会往 \(t\) 添加 \(x\) 一个数。
所以需要特殊考虑的数 \(x\) 都是在区间 \((\left\lfloor \frac{m}{3} \right\rfloor,\left\lceil \frac{m}{2} \right\rceil)\) 之间的，称这些数为特殊数。
如果两个数 \((a_0,a_1)\) 产生的非零余数序列分别为 \(a_{2},a_{3},...,a_{k-1},a_{k}\)，则 \(a_k\) 一定整除 \(a_{0}\sim a_{k}\) 的任何一个数，因为 \(a_k\) 就是 \((a_0,a_1)\) 的 \(\gcd\)。我们想把特殊数和非特殊数串起来，使得它们构成的非零余数序列可以被某个数对所产生，但这是不好做的。注意到一点事实：两个特殊数不会出现在同一非零余数序列中，否则开始的数对必定有一个数 \(\gt m\)。此外，考虑一个特殊数所在的非零余数序列，序列的最后一个元素必定整除这个特殊数。而我们直接把这两个数作为一个非零余数序列也是合法的。
这样，就转成了一个匹配问题：左部是特殊数，右部是非特殊数。最后的匹配大小应该就是 \(|L|\)，否则无解；而 \(R\) 中未被匹配到的数 \(x\) 都可以通过加入一组 \((3x,2x)\) 的形式进入 \(t\) 中，直接网络流即可。
点数是 \(O(n)\) 级别的，边数是 \(O(n^2)\) 级别的，众所周知网络流跑二分图最大匹配复杂度是 \(O(m\sqrt n)\) 所以时间复杂度 \(O(n^2\sqrt n)\)。实测最慢点 30ms，直接起飞。
1687
C. Sanae and Giant Robot
给出两个长度为 \(n\) 的序列 \(a_i,b_i\)。给出 \(m\) 个区间 \([l_i,r_i]\)。然后你可以执行任意次操作：
选择一个区间 \([l_i,r_i]\)，满足 \(\sum_{j=l_i}^{r_i}a_j=\sum_{j=l_i}^{r_j}b_j\)，然后对每个 \(j\in [l_i,r_i]\)，执行 \(a_j=b_j\)。
问是否可以将 \(a\) 变为 \(b\)。\(n,m\le 2\times 10^5\)。
送我上 IM 的题。
首先作差，令 \(c_i=a_i-b_i\)。则条件变为 \(\sum_{j=l_i}^{r_i}c_j=0\) 此时把 \(c_{l_i\sim r_i}\) 全部推平成 \(0\)，目标是让所有 \(c_i=0\)。
令 \(S\) 为 \(c\) 的前缀和，则条件变为 \(S_{l_i-1}=S_{r}=k\)，此时把 \(S_{l_i\sim r_i}\) 全部推平成 \(k\)，目标是让所有 \(S_i=0\)。
到这里我们发现一件事情，就是如果推平的时候 \(k\neq 0\)，那推了之后是不会更优秀的；如果 \(k=0\)，那我们执行一次推平一定是更优秀的。
所以我们可以每次找到一个没有被选中过的区间 \([l_i,r_i]\) 并且满足 \(S_{l_i-1}=S_{r_i}=0\)，然后把 \(S_{l_i\sim r_i}\) 中的所有非零位置全部推平成 \(0\)。考虑到一个区间最多被取出一次，一个位置最多被推平一次，各自可以用 set 去维护。时间复杂度均摊下来 \(O(n\log n)\)。（\(n,m\) 同阶）。
D. Cute number
记 \(g(x)=\left\lfloor \sqrt{x} \right\rfloor^2,f(x)=(g(x)+1)^2\)。称一个正整数 \(x\) 是好的当且仅当 \(x-g(x)\lt f(x)-x\)。
给出一个长度为 \(n\) 的正整数数组 \(a\)，求最小的非负整数 \(k\)。使得 \(a_1+k,a_2+k,...,a_n+k\) 这 \(n\) 个数字都是好的。
\(n\le 10^6,1\le a_1\lt a_2 \lt ... \lt a_n\le 2\times 10^6\)。
题目没有说会无解，明示我们 \(k\) 存在一个上界：显然最后的 \(g(a_1)\) 不超过 \((a_n+1)^2\)。
记 \(a=\sqrt{g(x)}\)，那么 \(a\) 不超过 \(a_n+1\)。也就是说 \(a\) 最后的取值也就是 \(O(a_n)\) 个，这启发我们暴力枚举最后的 \(a\)。
然后当 \(g(a_i)\neq g(a_{i+1})\) 的时候我们称新增了一个段，猜测所有情况的总段数加起来不会太多。因为你 \(a\) 特别大的时候，从 \(a\rightarrow (a+1)\) 实质上就跨越了 \(2a+a^2\) 个数，所以肯定最多跨越次数不会超过 \(\frac{a_n-a_1}{2a}\) 次，显然小于 \(\frac{a_n}{a}\) 次，那么所有 \(a\) 的跨越次数加起来就是 \(O(a_n \log a_n)\) 级别的。
从上面，我们知道了首先可以暴力枚举 \(a\)，然后把 \(a_1,a_2,...,a_n\) 按照 \(g(a_i)\) 去分组。但是对于每一组，我们还不明确具体做什么。
我们来研究一下条件中的式子。那么有 \(a^2\le x\lt (a+1)^2\)，然后 \(x-a^2\lt (a+1)^2-x \Leftrightarrow x\le a^2+a\)。
下面方便起见更改定义： \(g(x)=\sqrt{g(x)}\)。
不妨设 \(k\) 是最小的非负整数使得 \(g(a_1+k)=a\)。然后此时有些 \(a_i+k\) 是不会合法的。现在的问题是我们可能还要让 \(k\) 加上一个调整量 \(k'\) 使得所有 \(a_i\) 满足条件。而这个过程中，如果 \(a_i+k\) 合法，则 \(g(a_i+k)\) 应该等于 \(g(a_i+k+k')\)，否则 \(g(a_1+k+k')\) 一定不是 \(a\) 了。而对于不合法的 \(a_i+k\)，在保证 \(g(a_1+k+k')\) 不变的情况下，它如果想最后合法，则 \(g(a_i+k+k')=g(a_i+k)+1\) 必须成立。而此时你可以找到这一组内最小的 \(a_i\) 满足 \(a_i+k\) 不合法。所以对于每一段你只要找两个位置。而且它们是相邻的，实质上你只需要二分一次。
总复杂度 \(O(a_n \log a_n \log n)\)。
1691
E. Number of Groups
给出 \(n\) 条线段 \([l_i,r_i]\)，每条线段要么是红色，要么是蓝色，记为 \(c_i=0/1\)。
两条线段若异色且有交，则在它们之间连一条无向边。
问最后的连通块个数。\(n\le 10^5,1\le l_i,r_i\le 10^9\)。
考虑离线处理这个问题。离线处理线段/区间的常用套路是扫描线。
离散化 \(l,r\) 后从小往大枚举 \(x\)，若 \(x=l_i\) 加入线段 \(i\)，若 \(x=r_i\) 则删除线段 \(i\)（先处理所有加入，后处理所有删除）。然后加入一条线段时，所有加入过且未被删除的线段就是和它有交的。
显然我们要把线段分成两种颜色存储。每次找异色且与其有交的线段合并即可。但这样不能保证复杂度。特别地，注意到合并过后，异色的集合，只用保留 \(r\) 最大的那条线段即可。时间复杂度降为 \(O(n\log n)\)。