260614 - 260624

后期效率极其低下，警示。

P9170 [省选联考 2023] 填数游戏

建出 \(m\) 个点 \(n\) 条边的无向图，第 \(i\) 条边连接 \(T_i\) 中的两个点，那么 Bob 相当于是给边定向，使得每个点的入度不超过 \(1\)。那么对于一个连通块，如果 \(|E|>|V|\) 就无解，如果 \(|E|=|V|\) 那么是一棵基环树，我们求出正着绕环产生贡献的边、反着绕环产生贡献的边，总是产生贡献的边和都能产生贡献的边，策略就是分配第四者使得两种绕法的代价尽可能接近。如果 \(|E|=|V|-1\) 是一棵树，一条边形如固定或选择给内子树或者外子树答案 \(+1\)，最终要最大化答案的最小值。那么策略显然形如选一个点作为根，每条可选的边都给外子树加一，换根即可。

P10219 [省选联考 2024] 虫洞

我们首先说明一些关键性质，依次加入颜色为 \(d\) 的边，连接若干连通块，那么根据题目要求，被连接的连通块一定全部同构；并且，连接两个连通块之间的一条边，立即确定两个连通块颜色为 \(d\) 的出边（全部指向另一连通块）或入边。那么，颜色为 \(d\) 的边就是将一些连通块串成了一个大环，我们要说明这样能得到的本质不同图的数量等于原先连通块的大小。

考虑归纳，假如已经加入了 \(1\sim d\)，我们说明对于一个连通块 \(S\)，对于任意两点 \(u,v\in S\)，通过有序对 \((u,v)\) 确定一个 \(d\) 维向量 \((p_1,p_2,\cdots,p_d)\)，其中 \(p_i\) 是小于 \(i\) 颜色边连接连通块数的非负整数；并且通过 \(d\) 维向量唯一确定一个 \(S\) 的同构置换，其中 \((u,v)\) 属于该置换。

考虑归纳 \(d-1\to d\)，令 \(p_d\) 为 \(u\) 沿着 \(d\) 边向前走几步可以到达 \(v\) 所在的连通块，随后由于中间的 \(d\) 边都是同构映射，我们可以得到 \(u\) 连通块向 \(v\) 连通块的同构映射 \(P\)，进而令 \(p_{1\sim d-1}\) 为 \((P(u),v)\) 在 \(d-1\) 级连通块确定的向量。

随后我们证明映射 \(Q:x\to y,~y\) 是 \(x\) 向后走 \(p_d\) 条 \(d\) 边，再在 \(d-1\) 级连通块内部复合映射 \((p_1,\cdots,p_{d-1})\) 得到的点，该映射是 \(S\) 的同构映射。考虑把 \(d\) 边连成的环拉出来，设 \(cnt\) 个小连通块分别为 \(S_{1\sim cnt}\)，\(S_{i}\to S_{i\bmod cnt+1}\) 之间的 \(d\) 边对应的同构映射为 \(P_i\)，不妨设 \(P_{1\sim cnt-1}\) 都是单位置换，因此对于不在 \(S_{cnt}\) 内的点 \(u\)，\(\delta_d(u)\to \delta_d(P(u))\) 仍然属于 \(P\)。考虑对 \(u\in S_{cnt}\) 说明这件事，即说明 \(P_{cnt}^{-1}(p_1,\cdots,p_{d-1})P_{cnt}=(p_1,\cdots,p_{d-1})\)，也就是 \(d-1\) 级连通块的同构置换两两可交换。仍然考虑归纳，设当前复合两个置换 \((p_1,\cdots,p_d)\) 和 \((q_1,\cdots,q_d)\)，其结果为 \(((p_1+q_1)\bmod cnt,\cdots)\)，当且仅当 \(p_1+q_1\ge cnt\) 后面的排列需要额外复合一个 \(P_{cnt}\)，显然可交换。

因此，连接 \(d\) 边形成的本质不同连通块数量就等于 \(P_{cnt}\) 的方案数也就是连通块大小。考虑解决原问题，我们需要先求出同构连通块的等价类，然后对每个等价类分别解决。设 \(f_i\) 表示大小为 \(i\) 的本质不同的连通块数量，那么转移：\(f'_{i}=\sum_{j|i}jf_j\)，这样只对有倍数关系的二元组进行转移，矩阵乘法实际上是 \(O(n\log^2 n)\) 的。如果初始连通块大小不是 \(1\)，那么多出的贡献就是 \(sz^k\) 再乘以填入连通块的方案数，考虑找到最小值所在的连通块，其它连通块是任意填在其它位置的，还可以任意旋转，所以再乘一个 \((cnt-1)!sz^{cnt-1}\)，最后 \(\exp\) 起来即可。

考虑如何找等价类，对每个连通块记录从最小的点 \(x\) 到每个点对应的向量，压成整数。合并时只需从最小的点出发，看绕一圈会回到连通块的哪个点，得到 \(P_{cnt}\)。把 \(d-1\) 级图的哈希、\(P_{cnt}\) 和 \(cnt\) 哈希一下作为新连通块的哈希。再计算出 \(x\) 到 \(S\) 中的所有点对应的新映射 \((p_1,\cdots,p_d)\) 即可。时间复杂度 \(O(nm+n\log^2n\log k+n^2)\)

P9069 [Ynoi Easy Round 2022] 堕天作战 TEST_98

可以倍增值域分块做到 \(O(n\log n\log V)\)，但是常数较大。考虑维护区间最小值和次小值，如果最小值 \(<x\) 就向下递归，如果最小值 \(>x\) 就整体打标记，否则如果次小值大于 \(2x\) 就整体打标记，否则向下递归，每个数最多减半 \(\log V\) 次。时间复杂度 \(O(n\log n\log V)\)。

260616 B

相当于把 \(s_r\oplus s_{l-1}\) 放到区间线性基的最大答案。这样做非常困难，注意到答案等于 \(s_r\) 在线性基里的最大答案异或 \(s_{l-1}\) 在线性基里的最小答案，证明考虑每个能控制的位肯定是一个 \(1\) 和一个 \(0\)。然后又因为选定一个右端点，左边只有本质不同的 \(m\) 种线性基，所有 \(s_r\) 的最大答案可以处理出来；每个左端点对应的线性基也只有 \(m\) 种，其最小答案也可以处理出来。每当左端点的线性基和答案发生变化的时候，在 Trie 树上修改一下，在右端点处在 \(m\) 棵树上都查询一下，套个二分可以做到 \(O(nm^3)\)。

考虑建立可持久化 Trie，变为时间和空间都是 \(O(nm^2)\)，空间不够。

把所有修改都离线下来，直接在 Trie 上二分答案，我们本质只关心深度为当前层的子树和，可以用 umap 简单维护。空间 \(O(nm)\)。

260616 C

\(p=0\) 或 \(p=1\) 可以判掉。我们先证明剩余情况一定收敛，只需证明 B 以最优策略行动时会在有限步内结束，因为有限步内恰好走出最优策略的概率非 \(0\)，因此一定会出现。构造考虑 B 不断把 \(0\) 翻成 \(1\)，直到 A 第一次选择把 \(1\) 翻成 \(0\)，之后 B 不动。如果 A 不行动那么 B 直接获胜，否则反着读的二进制数严格变小，必在有限次内变为全 \(0\)，此时 B 全部翻转即可。

两种策略混合比较难以处理，考虑 B 采取最优策略的情况，依旧倒着 bfs，一种局面能恰好被两种局面转移到，一种该 A 行动，一种该 B 行动。又注意到这两种局面一定是同时被 bfs 到。由于是 bfs 所以该 A 行动的局面一定会采纳第一次遍历的距离，该 B 行动的局面一定会采纳第二次遍历的距离，所以每次只会扩展恰好一个点，也就是所有局面的答案取遍 \(0\sim 2^n-1\)，两人的最优策略构成一条链。

然后改成 B 随机的情况，随机选择要么选到最优策略 \(-1\)，要么返回之前的某个点。不难说明 A 总会采取原先的最优策略，所以转化成经典问题，线性 dp 即可，复杂度 \(O(2^n)\)。

P9987 [Ynoi2079] riapq

考虑将贡献 \([l,x]\to x\) 差分成 \([1,x]\to x\) 和 \([1,l-1]\to x\)，前者用树状数组维护系数（卡常时当然不要写分块），考虑对后者用分块维护，整块对整块可以通过简单打标记实现，整块对散块可以通过预处理后暴力修改实现，散块对散块直接预处理排序结果可以做到 \(O(B)\)，散块对整块考虑用树状数组和差分（本质是一个 \(\frac{n}{B}\times n\) 的平面上的在线二维数点），改成逐块处理会变快很多，可能是因为在几百兆的空间中随机访问比在不到一兆的空间内随机访问慢很多。

qoj18556 Buy for More, Sell for Less

把没用的都扔掉，剩下的物品差价严格下降，原价严格上升。按照第一步购买的物品将容量划分为 \(n\) 个区间，区间内 \(+1\) 的点形成一个等差数列，维护即可。

18338. Discount Event

其实是查路径上所有旁子树的答案的合并，显然可以倍增，需要在链上支持三删一，在 \(\text{lca}\) 处支持四删二。

qoj18370 Map1e

全都乘 \(9\)，从大到小枚举答案 \(x\)，考察 \(N\bmod 10^x-1\) 的余数，考察每一位的贡献，形如 \(1,10,100\cdots 10^{x-1},1,10,100\cdots\) 的循环，可以在线性预处理后 \(O(\frac{n}{x})\) 查询出余数模大质数的结果。要判断该数是不是 \(10^x-1\) 的一个倍数模大质数的值，发现商的范围也只是 \([0,\frac{n}{x}]\)，所以枚举商并判断即可。

260618 B

有 \(n\) 个点，有 \(m\) 个三元组 \((l_i,r_i,u_i)\)，表示你可以连接一条 \(u_i\to v_i\in [l_i,r_i]\) 的一条边，问能否使图连通。

\(n,m\le 2\times 10^5\)

已知 \(n-1\) 条边形成树的必要条件是对任意点集 \(S\)，完全包含于其中的边不超过 \(|S|-1\) 条，猜测这是充分的，考虑构造。这个东西和霍尔定理很像，考虑把区间右端点都减一，转化为选一些区间，区间的并的长度至少为区间数量，因此存在区间向 \(n-1\) 个 gap 的完美匹配。

于是考虑从左往右处理每个 gap，钦定右侧的 \(n-i+1\) 个点是 \(n-i+1\) 个连通块的代表元，那么如果区间的固定点和 \(i\) 在一个连通块就和 \(i+1\) 连接，否则和 \(i\) 连接，归纳即可。考虑如何找到一组完美匹配，显然可以贪心。

260618 C

有一个 \(A\times B\times C\) 的立方体，有一张 \(n\times m\) 的纸，初始时长为 \(A,B\) 的两条棱分别紧贴纸的上边缘，左边缘。每次你可以沿着立方体与纸接触的一条棱将立方体旋转 \(90\) 度，使得最终它的其中两条棱分别紧贴纸的下边缘和右边缘。问立方体滚过面积的最大值。

\(A,B,C,n,m\le 10^6\)

方块的本质不同状态实际上形成一个长度为 \(6\) 的环，显然只要每条边被经过的次数相同，顺序是可以改的。于是枚举有没有走过一个完整的环，否则枚举走了哪些边，走过的边可以反复走，是一个背包问题，复杂度 \(O(6^2n)\)。

uoj681 月球列车

直接对每一位预处理排序并二分可以做到 \(O(q\log n\log V)\)。考虑优化，由于高一位形如把低一位分成两个子序列并放到左右两边，所以通过预处理我们实际上可以 \(O(1)\) 从低一位的位置递推到高一位的位置上。复杂度 \(O((n+q)\log V)\)。

260623 B

有一个长为 \(n\) 的 \(01\) 序列和 \(m\) 次操作，每次操作形如 add 表示选择一个 \(0\) 变成 \(1\)，test x 0/1 表示钦定下标 \(x\) 当前为 \(0/1\)，随后立即置为 \(0\)。每次操作之后，你需要求出有多少个位置必然是 \(0\)，多少个位置必然是 \(1\)。

\(n,m\le 10^5\)

考察每次 add 可以操作的位置集合，一次 test 1 形如选一个候选集合包含当前位置的 add，然后将当前位置从之前所有操作的候选集合中移除，一次 test 0 形如直接移除，一次 add 形如新增一个候选集合为全集的操作。考察如何计算答案，由于所有候选集合按照时间的先后顺序具有包含关系，所以如果一系列集合的并集大小等于集合数量，那么这些位置都立即被确定为 \(1\)；不在候选集合里的数都被确定为 \(0\)；不难说明其他数都不能确定。用线段树之类的东西简单维护即可。

P13272 [NOI2025] 序列变换

首先钦定不允许进行没有用的操作。一段有关的操作形如一段前缀从左往右，每次 \(a_{i+1}\gets a_{i+1}-a_i\)，一段后缀从右往左，每次 \(a_i\gets a_i-a_{i+1}\)。其实可以知道中间剩下那个数的值为区间内所有和它距离为偶数的点减去距离为奇数的点，那么这样直接划分就是不会算重的，因为两个本质相同但其中一个端点不同的两个段，相差的那段必定为 \(0\)，因此不能操作过来。

预处理以每个位置为左右端点，向两边最多进行多少次操作。然后分讨区间内的奇偶位置之差，可以知道最终剩下的数在奇数位置还是偶数位置，再根据两个端点的限制就可以知道最终剩下的数可以在哪几个位置。复杂度 \(O(n^2)\)。