25.06-三轮省集模拟赛题解

· · 题解

风物长宜放眼量。心胸要开阔。

由于水平有限，只补了一部分题，因此只有这部分题解。

D1T1 人渣的本愿

题意

给定一棵树，初始每个点信息为 (0,0)，需要支持单点查询。修改为对 x 到根路径上所有点 u 操作，若 (a_u,b_u) 中 a_u\ne c 则将其修改为 (c,z)，其中 z 为本次操作编号。n,q\le 10^6。

题解

先考虑链的做法，用线段树进行区间修改，则要给区间内所有点合并上 (c,z)。然而线段树需合并懒标记，会先将后面的操作合并，直接维护可能出错。例如操作依次为 (x,a),(y,b),(x,c) 时，可能在懒标记上先合并后两个得到 (x,c)，再跟 (x,a) 合并得到 (x,a)，然而结果应为 (x,c)。

该错误启发我们对 (a,b) 额外记录一个布尔变量 f，表示操作 b 之前是否存在值不为 a 的信息，这样 t_0=(a_0,b_0,f_0) 和 t_1=(a_1,b_1,f_1) 合并时若 a_0\ne a_1，答案为 (a_1,b_1,1)，否则答案为 t_{f_1}。事实上该标记具有结合律，正确性得到保证，可以用懒标记线段树做到 O(n\log n)。

再把该做法放到树上，显然可以直接树剖做到 O(n\log^2 n)。又因为修改是点到根的路径，直接使用全局平衡二叉树就可以做到 O(n\log n)，常数较大，跑不过颜色段均摊 + LCT 或树剖。

D1T2 宝石之国

题意

给定两维大小均为 n 的平面上的 n 个矩形。对于所有 im\le n 的 i，求恰好被 im 个矩形包含的面积大小。\sqrt{n}\le m\le n\le 3\times 10^5。

题解

考虑对一维扫描线，将矩形加差分为区间加。为方便统计贡献使用分块维护，块内开桶记录个数，每次遍历所有块并枚举所有询问累加答案，时间复杂度为 O(\frac{n^3}{Bm}+nB+\frac{n^2}B)。注意到瓶颈在前两项，对其平衡得到 B=\frac n{\sqrt m} 时复杂度为 O(\frac{n^2}{\sqrt m})，由 m 范围可得 m=\sqrt n 时取到最大为 O(n^{\frac 74})，难以通过。

再考虑记录每个块内的最值，只统计值域区间内的贡献，这样统计某个块的复杂度为 O(\frac {\max-\min} m)，因此单轮复杂度只与所有块的极差之和有关。注意到只有散块操作可能使某块的极差增大 1，因此所有块的极差之和为 O(n)，每轮统计贡献的复杂度为 O(\frac nm)。

这样优化后总复杂度为 O(\frac {n^2}m+\frac {n^2}B+nB)，对后两项平衡并取到最大，即 B=m=\sqrt n 时，复杂度为 O(n\sqrt n)，可以通过。具体实现时由于差分出的加减操作区间相同，可以不用在桶上维护最值，只需记录目前散块操作值的和 d，值域即为 [tag,tag+d]，这样写常数会小不少。

D2T1 哩哩哩啦哩啦

题意

给定一棵树，要求选择编号在某个区间 [L,R] 内的所有点。有 m 条形如 (u,k) 的限制，表示 u 点的 k 级后代中至少要选择一个点，求合法 [L,R] 中 R-L 最小的。n,m\le 2\times 10^5。

题解

之后把这些限制区间内的编号拿出来分别排序，然后枚举最终的 $L$，用指针维护每个区间内最小的合法 $x$，取这些编号的最大值为最优的 $R$，扫一遍即可得到答案。由于区间两两不交，这里复杂度为 $O(n)$。总时间复杂度为 $O(n\log n)$，来自排序和二分。 ### D3T2 还原论 #### 题意 维护序列 $a$，需要支持区间变为异或差分，单点查询，最后输出整个序列。$n\le 2.5\times 10^5,q\le 10^5,a_i<2^{30}$。 #### 题解 先考虑 D 性质，即 $l=1,r=n$ 的情况。此时若进行了 $x$ 次操作，则目前 $a'_i=\bigoplus_{j\subseteq x}a_{i-j}$，其中 $j\subseteq x$ 表示二进制下 $j$ 为 $x$ 的子集。证明可考虑 $x$ 行的网格图，其所有格中均存在左上到右下的对角线，要求只能向下或右下走。则 $a_{i-j}$ 对 $a'_i$ 的贡献次数即为 $(0,i-j)$ 到 $(x,i)$ 的路径条数 ${x}\choose{j}$，根据卢卡斯定理可得当且仅当 $j\subseteq x$ 时有 ${x\choose j}\equiv 1\pmod 2$，$a_{i-j}$ 对最终 $a'_i$ 有贡献。 然而 $x$ 较大时无法直接枚举子集，考虑定期重构，每当 $x=B=2^k$ 时更新整个序列并将 $x$ 清空。注意到此时子集只有 $0$ 和 $2^k$，可以 $O(n)$ 更新，复杂度为 $O(\frac{nq}B)$。这样查询时 $x$ 不会超过 $2^k$，直接枚举子集即可，复杂度为 $O(qB)$。取 $\sqrt n$ 附近的 $2^k$ 作为 $B$，得到总复杂度为 $O(q\sqrt n)$。 变为区间修改时，仍对每 $B$ 个修改分一块，回答其内部的询问，同时更新出整个序列在这 $B$ 次修改后的值。注意到由于修改次数不超过 $B$，此时 $a'_i$ 的值只受 $[i-B,i]$ 内 $a$ 值的影响。因此我们再对序列每 $B$ 个元素分一块，则某块内元素的值只受该块和前一个块影响。因此可以先枚举操作块，再枚举序列中每个块依次处理，此时只需要考虑序列中的两个块。 具体地，处理块 $i$ 时拿出块 $i,i-1$，若修改完全包含两个块则只累加 $x$ 标记；若修改只包含两块的一部分，则要清空 $x$ 标记并重构两个块，再进行区间暴力修改。对于某个在块 $i$ 内的询问，可将标记清空再查单点值，或直接枚举 $x$ 的子集求答案。这里清空标记不能暴力枚举所有 $x$ 的子集，而是要进行类似高维前缀和的操作，即枚举每个 $x$ 是 $1$ 的二进制位 $2^k$，并倒序更新所有 $a_i\leftarrow a_{i}\oplus a_{i-2^k}$，容易发现这样操作的结果与暴力枚举子集相同，复杂度 $O(B\log B)$。 现在计算复杂度。有 $O(\frac nB)$ 个序列块，区间修改影响至多四个块，处理时标记清空复杂度 $O(qB\log B)$，暴力更新复杂度 $O(qB)$。每次查询时若清空标记有 $O(qB\log B)$ 的复杂度，若暴力枚举子集有 $O(qB)$ 的复杂度。另外有 $O(\frac qB)$ 个操作块，每个操作块处理完后需下放所有序列块的标记，复杂度 $O(\frac{nq}{B^2}B\log B)=O(\frac {nq\log B}B)$。综上所述总复杂度为 $O(qB\log B+\frac{nq\log B}B)$，取 $B=\sqrt n$ 可得 $O(q\sqrt n\log n)$。[这里](https://www.luogu.me/paste/j9sn4jy5)给出了特殊性质和两种答案统计方式的代码，其中枚举子集的常数较小。 #### 原题 [P10009](https://www.luogu.com.cn/problem/P10009)。 ### D3T3 无论 #### 题意 给定长为 $n$ 的数组 $a,b$，可对 $a$ 数组操作，每次可选一段区间 $[l,r]$，将其中所有非零元素均加一或均减一，求将 $a$ 变为 $b$ 的最少操作次数。多测，$n\le 10^6,\sum n\le 3\times 10^6,a_i,b_i\le 10^9$，其中 $30\%$ 满足 $T\le 10,n\le 3000,a_i,b_i\le 500$。 #### 题解（30 分） 首先可以把 $b_i=0$ 的连续段缩成一个点，其 $a_i$ 值为原区间 $a_i$ 的最大值，容易证明这是等价的，因为减到 $0$ 后多减几次不会有影响。以下均认为 $b$ 中不存在连续的 $0$。 注意到在令每个点的减操作在加操作之前时一定能取到最优解。证明考虑先加后减一定能复原，因此对于某种操作序列，若存在 $[l_1,r_1]$ 加在 $[l_2,r_2]$ 减之前且这两个区间有交，不妨设 $l_1\le l_2\le r_1\le r_2$，则可将 $[l_2,r_1]$ 内的两次操作抵消，变为 $[l_1,l_2-1]$ 加和 $[r_1+1,r_2]$ 减，可调整为不劣的合法操作序列。 此时便可以把加减操作分开考虑，以下令 $c_i$ 为减操作次数，$c'_i$ 为加操作次数。若操作次数序列为 $x$，则有最小操作次数 $\sum_{i=1}^n \max(x_i-x_{i-1},0)$，据此可设计 DP 状态，拆贡献统计答案。注意到若 $b_i\ne 0$，则限制为 $c_i<a_i$，且有 $c'_i=b_i-(a_i-c_i)$。然而若 $b_i=0$ 就只有 $c_i\ge a_{i}$ 的限制，不好确定 $c'_i$。这时 $b_{i-1}\ne 0$，可通过 $c_{i-1}$ 确定 $c'_{i-1}$，再令 $c'_i=c'_{i-1}$ 一定不劣，事实上取在 $[\min(c'_{i-1},c'_{i+1}),\max(c'_{i-1},c'_{i+1})]$ 内都是最优的。 因此设 $f_{i,j}$ 表示考虑了前 $i$ 个数且 $c_i=j$ 的最小总贡献。转移时若 $b_{i-1}\ne 0$ 则枚举 $f_{i-1,j}$ 转移，容易计算出操作次数。若 $b_{i-1}=0$ 则有 $b_{i-2}\ne 0$，可枚举 $f_{i-2,j}$，推出 $c_{i-1}=\max (a_{i-1},j))$，再计算 $i-1,i$ 的贡献转移。时间复杂度 $O(TnV^2)$，实现上若只使用合法的 $(i,j)$ 状态转移，常数较小，可以通过 $n\le 3000$ 的数据。 感觉这个 DP 很有思维价值，因此将该部分分记录于此。正解是对该 DP 观察性质并优化到线性，包括凸性和差分数组不超过 $2$ 之类，不是很懂，不管了。 ### D4T1 象形文字 #### 题意 给出长分别为 $n,m$ 的序列 $a,b$。奇数轮删掉 $a$ 中最大值，偶数轮删掉 $a$ 中最小值，之后拿出 $b$ 中任一元素插入 $a$ 中任意位置，此为一轮操作。求最少多少轮可令 $a$ 序列单增。$n\le 10^5,m\le2\times 10^5$。 #### 题解 设 $p_i$ 表示 $i$ 在 $a$ 中的位置，考虑枚举一段值域区间 $[l,r]$，钦定该区间外的所有数均被删，区间内保留一段子区间。为了最终 $a$ 序列单增，要求 $[l,r]$ 内的 $p$ 数组也单增。由于统计了最终保留其子区间的答案，只需要枚举极长的合法区间即可。 之后记 $ca,cb$ 分别表示 $a$ 中小于 $l$ 和大于 $r$ 的个数，$ta,tb$ 分别表示 $b$ 中小于 $l$ 在 $a$ 中前驱和大于 $r$ 在 $a$ 中后继的个数。该区间是否合法以及最少操作轮数只与这些值有关，之后是一些个人认为意义不大的分讨，此处略去。时间复杂度 $O(n)$。 ### D5T2 互相抵消 #### 题意 维护序列 $a$，需要支持区间加，区间查询 $\sum_{l'=l}^r\sum_{r'=l'}^r ((\sum_{i=l'}^{r'}a_i)^2+(r-l+2)(r'-l')a_{l'}a_{r'})$，取模。$n,q\le 5\times 10^5$。 #### 题解 考虑把两部分拆开，对 $\sum_{l'=l}^r\sum_{r'=l'}^r (\sum_{i=l'}^{r'}a_i)^2$ 进行转化。注意到后面有 $a_{l'}a_{r'}$ 的乘积形式，因此将平方拆成两个括号中各选一项，再对每一组 $a_ia_j$ 求能贡献到的 $[l',r']$ 个数，可得 A： $$\sum_{i=l}^r (i-l+1)(r-i+1) a_i^2+\sum_{i=l}^r\sum_{j=i+1}^r2(i-l+1)(r-j+1)a_ia_j$$。 后面部分再进行一些转化，把 $2$ 的系数拆开，得到 B： $$\sum_{i=l}^r\sum_{j=i+1}^r(i-l+1)(r-j+1)a_ia_j+\sum_{j=l}^r\sum_{i=j+1}^r[(i-l+1)+(j-i)][(r-j+1)+(j-i)]a_ia_j$$。 把后面拆开得到 C： $$\sum_{j=l}^r\sum_{i=j+1}^r[(i-l+1)(r-j+1)+(r-l+2)]a_ia_j$$。 把 B 前半部分和 C 前半部分结合，得到 D： $$(\sum_{i=l}^r(i-l+1)a_i)(\sum_{j=l}^r(r-j+1)a_j)-\sum_{i=l}^r(i-l+1)(r-i+1)a_i^2$$。 有 D 后半部分与 A 前半部分抵消，C 后半部分与原式后半部分抵消，得到所求即为 $(\sum_{i=l}^r(i-l+1)a_i)(\sum_{j=l}^r(r-j+1)a_j)$。用数据结构维护 $a_i,ia_i$ 的和即可，时间复杂度 $O(q\log n)$，比较卡常，可能需要用树状数组实现。 ### D6T1 黄金之心 #### 题意 给出 $V,n,k$，求字符集大小为 $V$，长度为 $n$，且不存在长为 $k$ 的回文子串的字符串数量，取模。$V\le 10^9+7,n\le 1000,k\le 25$。 #### 题解 考虑容斥，即设 $g_x$ 表示有至少 $x$ 个回文子串的字符串数量，则答案为 $\sum_{x=0}^{n-k+1}(-1)^xg_x$。考虑若钦定了某些子串回文，则每个回文子串的每个对应位置均在同一个等价类内，这种钦定方式的方案数即为 $V^c$，其中 $c$ 为等价类个数。这告诉我们 DP 状态不需要记回文串数量或等价类数量，只需要统一放在 DP 值里即可，可以通过带上 $-1$ 或 $V^x$ 转移。 注意到 $k$ 很小，考虑直接设 $f_{i,S}$ 表示考虑了前 $i$ 位，其中最后 $(k-1)$ 位的并查集状态为 $S$ 时带容斥系数的方案数，$S$ 是一个长为 $(k-1)$ 的数组，其中的并查集使用最小表示防止状态数增多。转移是容易的，枚举以 $i$ 结尾的子串是否回文即可，不回文则系数为 $V$，回文则系数为 $-V^{1-c}$，其中 $c$ 为减少的等价类数量。 注意到用等长回文串合并等价类时限制较多，因此合法 $S$ 的数量应该不多，远不到 Bell 数级别。事实上暴搜一下发现 $k=25$ 时只有 $T(25)=90483$ 种，且每种只会转移到其他两种状态，转移数量也是 $O(T(k))$ 的，提前预处理所有转移即可。时间复杂度为 $O(nT(k))$，可以通过。 ### D6T2 超级电脑 #### 题意 设序列权值为其所有子序列的异或和之和，给定 $n,m,x$，求最小的 $k$ 使得长为 $n$，权值为 $k$ 的序列数量对 $m$ 取模为 $x$，对大质数取模输出。多组测试，$T\le 100,n\le 10^{10^4},x<m\le 10^9$。 #### 题解 考虑序列权值的计算方式，对于每个二进制位，若存在 $1$ 则有 $2^{n-1}$ 种包含奇数个 $1$ 的子序列，否则没有贡献。因此序列权值为 $2^{n-1}V$，其中 $V$ 为所有数的按位或值。所以当 $2^{n-1}\mid k$ 时有 $V=\frac{k}{2^{n-1}}$，方案数为 $(2^n-1)^c$，其中 $c$ 为 $V$ 中 $1$ 的个数；不整除时方案数为 $0$。 反过来由 $x$ 构造 $k$ 时，要求 $(2^n-1)^c\equiv x\pmod m$，使用扩展 BSGS 求出最小的 $c$，答案即为 $(2^c-1)\times 2^{n-1}$。所有 $2^n$ 均需要使用扩展欧拉定理降幂求解，细节此处不表。还有 $n,x,m$ 为 $0,1$ 时的诸多边界情况，此处均略去。总时间复杂度可以做到 $O(T(\sqrt m+\log n))$。 ### D7T1 Kanade 的水杯 #### 题意 有 $n$ 个水杯，分别有容量 $a_i$，初始第一个满，其余空。对 $i\in[1,n]$ 依次操作，等概率选择一个其他水杯，将第 $i$ 个水杯中的水倒入，直到该杯满或第 $i$ 个杯空。对每个水杯求其最终期望水量。$a_i\le n\le 10^5$。 #### 题解 注意到 $i$ 水杯操作时，其后所有水杯一定为空，因为同时只会存在只多一个有水且未操作的水杯。因此若所选的目标 $j<i$，之后的操作均可忽略。另外 $j<i$ 时转移水量一定为 $\min(a_j,b_i)$，其中 $b_i$ 为目前 $i$ 的水量。当 $j$ 为空时显然，$j$ 不空时 $b_i$ 一定是从 $j$ 中转移来的，因此该式必然取到 $b_i$，该结论成立。 据此可设计 DP 状态，设 $f_{i,x}$ 表示操作到 $i$ 时其水量为 $x$ 的概率，则可以转移给 $j>i$ 的 $f_{j,\min(a_j,x)}$，或是直接给 $j<i$ 的 $j$ 累加上 $f_{i,x}\times\min(a_j,x)$ 的答案，两处都还要乘上 $\frac 1{n-1}$ 作为系数。这样要枚举 $i,x,j$ 三维，复杂度为 $O(n^3)$。 注意到所有转移均与 $i$ 无关，而只与 $i,j$ 的大小关系有关。考虑使用前缀和优化，设 $s_{i,x}=\sum_{j=1}^i f_{i,x}$，则可以枚举 $j,x$ 两维转移，转移式与上面相似，复杂度为 $O(n^2)$。此处为了保证复杂度，需要预处理存在 $x$ 单位水时向外转移的总剩余量 $c_x$，答案还要累加上 $\frac 1{n-1}\sum_{x=1}^n c_xf_{i,x}$。 再次观察转移过程，发现对于 $x>a_i$ 有 $f_{i,x}=0$；对于 $x<a_i$，有 $f_{i,x}=\frac1{n-1}s_{i-1,x},s_{i,x}=s_{i-1,x}+f_{i,x}=\frac n{n-1}f_{i-1,x}$；而 $f_{i,a_i}=\frac 1{n-1}\sum_{y=a_i}^n s_{i-1,y}$，据此也可以更新 $s_{i,a_i}$。注意到此处 $s$ 的变化只有区间乘和单点加，需要支持区间查。统计答案时将 $f$ 也差分成 $s$ 即可，还需要 $c_xs_{i,x}$ 和 $xs_{i,x}$ 的区间和。这些均可使用线段树维护，时间复杂度为大常数 $O(n\log n)$。 ### D8T1 Eileen 的游戏 #### 题意 给定两个长为 $n$ 的数组 $a,b$，元素两两不同。$q$ 次询问，每次给出 $l,r$，求有多少大小在 $[l,r]$ 内的集合 $S$ 满足存在排列 $p$，使得 $a_i>b_{p_i}$ 的 $i$ 组成的集合恰为 $S$。$q-1\le n\le 5000$。 #### 题解 首先枚举 $\left|S\right|=x$，考虑如何判断一个集合 $S$ 是否合法。此时令 $S$ 内元素与前 $x$ 小的元素匹配，$S$ 外元素与剩余元素匹配，且两部分均将 $a,b$ 分别从小到大排序后对应位置匹配一定不劣。因此先将 $a,b$ 排序，这样就可以设 $f_{i,j}$ 表示前 $i$ 个数中选进 $S$ 了 $j$ 个，且前 $i$ 个匹配均合法的方案数。转移时枚举第 $i$ 个数的情况，只进行合法转移即可。时间复杂度 $O(n^3)$。 考虑优化这个过程，注意到 $f_{i,j}$ 转移时若令其在 $S$ 内，则要 $a_i>b_j$，否则要 $a_i<b_{x+i-j}$。这里前者与 $x$ 无关，而后者有关，复杂度瓶颈也在这里。若把顺序倒过来，即 $g_{i,j}$ 表示 $[i,n]$ 中有 $j$ 个在 $S$ 外的合法方案数，则令其在 $S$ 外只需 $a_{i}<b_{n-j+1}$，否则需要 $a_{i}>b_{x-n+i+j}$，反而使得在 $S$ 外的判断不再依赖 $x$ 的值了。若能把不依赖 $x$ 值的两部分拼成答案，就可以降低复杂度。 考虑找到一个位置 $p$，使得其为 $a$ 中最后一个满足 $a_p<b_x$ 的位置，此时可以确定 $[1,p]$ 内的 $a_i$ 放到 $S$ 外一定合法，$[p+1,n]$ 内的 $a_i$ 放到 $S$ 内也一定合法，此时只需要保证前面放到 $S$ 内和后面放到 $S$ 外的匹配合法即可，这正是 $f,g$ 的转移中不依赖 $x$ 的那部分。因此只考虑这些限制转移出 $f,g$ 数组，对每个 $x$ 找到对应的 $p$，$\left|S\right|=x$ 的答案即为 $\sum_{j=0}^x f_{p,j}\times g_{p+1,n-i-p+j}$。对答案求前缀和即可回答 $[l,r]$ 的区间询问，时间复杂度为 $O(n^2+q)$。 #### 原题 [P12558](https://www.luogu.com.cn/problem/P12558)。