标签：2024.10 log 记录 sum leq 考虑复杂度 dp

$2024$ 年 $10$ 月记录

qwq。

20240929

联考 T3

考虑怎么快速判定一个图是否有四元环，可以度数小定向连到度数大的点，由三元环计数的分析方法，枚举 $i$ 相邻的 $u$，定向连出的 $v$，判定 $i,v$ 是否有向相邻，是 $O(m\sqrt m)$ 的。考虑 $u$ 的度数为 $d_u$，现在来分析一下 $m$ 足够大时不用判定直接输出有四元环：要求 $u,x,y$，满足 $u\ne x,x\ne y$，$x,y$ 为 $u$ 的邻居，不存在四元环的充要条件是这样的无序 $(x,y)$ 组是互不相同的。显然有 $\sum \binom{d_u}{2}\leq \binom{n}{2}$，现在分析 $m=\dfrac{\sum d_i}{2}$ 的量级，有 $\sum \binom{d_i}{2}=\dfrac{\sum d_i^2}{2}-m$，由柯西不等式 $\sum a_i^2\sum b_i^2\ge(\sum a_ib_i)^2$，有 $\sum\binom{d_i}{2}=\dfrac{\sum d_i^2}{2}-m\ge\dfrac{(\sum d_i)^2}{2n}-m=\dfrac{2m^2}{n}-m$。所以有 $\dfrac{2m^2}{n}-m\leq \binom{n}{2}$，可以化简得到 $m\leq \dfrac{n+n\sqrt{4n-3}}{4}$。因此对于 $m$ 超过这个阈值时直接输出 Yes，否则暴力判定即可。时间复杂度 $O(n^2+qn^{1.5})$。

CF878E

贪心真的会不了一点/ll。在直接开始做前，尽量找下最优解序列的性质，这个思想也体现在【NOIP2021】方差。

这不是我们公益模拟赛 D2T4 吗。考虑一个数的贡献系数必然是 $2^p$，那么 $p$ 必然满足其 $p_1=0$，并且 $\forall i>1,p_i>0,p_i\leq p_{i-1}+1$。特判一下 $p_l$ 的情况。注意到最终需要输出取模，中间的过程是无法使用取 $\max$ 的，因此一定是贪心。那么系数序列 $p_i$ 就可以划分为若干 $p_i=p_{i-1}+1$ 的连续段，我们希望正数的系数都尽可能大，负数的系数尽可能小。对于这个连续段 $[l,r]$，重要的性质是：如果一个连续段断掉了，下一段的起点一定是 $1$，也就是每个连续段一定满足从 $1$ 开始并且单调递增构成 $1\to r-l+1$。贪心的想法就是，如果 $a_i\ge 0$ 或者 $a_i<0$ 时 $i$ 开始的一个子段的贡献和是正的，直接让 $p_i=p_{i-1}+1$，否则让 $p_i=1$。因为 $p$ 整体加的影响就是给和乘上一个 $2^{\triangle p}$，正负性还是取决于原先的贡献。这样考虑询问怎么做。把询问放在右端点上，离线扫描线序列。考虑加入一个 $r$ 的影响，我们希望找到的连续段是尽可能长的，因为裂开成两段后，后面的贡献系数是劣的。我们可以维护 $[1,r]$ 的最优分段，只有可能出现一段后缀的连续段合并的情况，中间的由于之前已经最优了是不会二次合并的。可以不断往前合并块，直到这个块的和为负。这一过程可以用并查集快速维护。比较和的大小时注意如果 $w$ 已经足够大需要改成一个确定的 $+\infty$。如果 $l$ 不是连通块的起点断一下就好了。时间复杂度 $O(n\log n)$。

UOJ760

考虑方案数转概率的 trick，令 $f_u$ 表示 $a_u=1$ 的概率，$deg_u$ 表示出度，设个中间量表示 $g_{u,i}$ 为 $i$ 个儿子为 $1$ 的概率，期望 $t=\sum f_v$ 个儿子是 $1$，那么有 $\sum g_{u,i}i=t$。考虑转移就是 $f_u=\sum\dfrac{i}{deg_u}g_{u,i}=\dfrac{\sum f_v}{deg_u}$，那么考虑这个是线性的，求出每个叶子节点向上的贡献系数，线段树维护一下取反操作即可。算贡献的步骤需要前后缀拼合的套路。

UOJ757

维护 $f_{i,j,0/1}$ 表示第 $i$ 列的大坝建造到了第 $j$ 行，贡献是否算上了第 $i$ 列，容易发现对于一个大坝，建立的位置只有可能是 $n-1$ 或者所有鲶鱼 $y_i$ 对应的 $y_i-1$。这样做 dp 的有效状态数是 $O(n+m)$ 的。容易前缀和优化到 $O(n+m)$。

UOJ236

特殊图欧拉回路，同一题型的还有【统一省选 2020】丁香之路。

注意到 $t$ 是定的，但是 $s$ 是动的很烦，考虑改成 $=s$，并且提速不消耗代价，降速 $x$ 花费 $x$ 的代价。那么就是给定一堆 $s\to t$ 的边，以及一条 $+\infty \to 1$ 的边，需要加入最小边权和的额外边使得原图存在欧拉回路。其中额外边 $x\to y$ 的代价为 $\max(0,x-y)$。而在任意回路中，$(i,i+1)$ 被向左向右覆盖的次数应该都是相等的。考虑维护每个普通相邻边的总变化量，即多少个向左走多少个向右走的差值，最开始都是 $0$，因为被一个 $+\infty\to 1$ 抵消掉了。最终这俩相等这玩意是充分必要的，考虑增量构造：加入一条边之后能优化掉多少。注意到特殊边的作用是来抵消普通边代价的，那么求出来被覆盖的值 $d_i$，如果 $d_i<0$ 就必须往小的连边去抵消掉，否则可以无代价连边 $i+1$。每次就形如对区间进行区间 $+1$ 或 $-1$，可以差分维护。欧拉回路还要求连通，最后跑一遍 MST 合并即可。时间复杂度 $O(n\log n)$。

20240930

UOJ836

场上拿到了 $35$ 分/fn。

判掉平凡的两端相等的情况，不妨设 $a_1<b_1$，考虑 $f_{i,j}$ 表示 $A[1:i],B[1:j]$ 是否可行。初始有 $f_{1,1}=1$。有转移 $(f_{i-1,j}\text{ or }f_{i,j-1}\text{ or }f_{i-1,j-1})\text{ and }[a_i<b_j]=f_{i,j}$。放到二维平面上，就是考虑将 $a_i\ge b_j$ 的点 $(i,j)$ 视为障碍，判定是否存在 $(1,1)\to (n,m)$ 的八连通路径。对于特殊性质的做法，因为 $x_n<x_1<y_1<y_m$，保证了第 $n$ 行与第 $m$ 列都是空的。也就是说只要能走到第 $n$ 行或者第 $m$ 列，就可以直接下来。显然如果出现 $x_{\min}\ge y_{\min}$ 或者 $x_{\max}\le y_{\max}$ 时就寄了。那么考虑如何抵达第 $n-1$ 行或第 $m-1$ 列。如果 $x_{\min}<y_{\min}$ 就可以递归的将 $n$ 改为 $\text{argmin}(x)$，同理 $x_{\max}<y_{\max}$ 可以将 $m$ 改为 $\text{argmax}(y)$。双指针模拟这个过程即可。对于没有特殊性质，找出来 $x$ 的全局 $\min$ 和 $y$ 的全局 $\max$，对于两个部分分开跑一下就行。时间复杂度 $O(nq)$。

原神模拟赛 D3T2

“构造题？狗叫题！！”

原神模拟赛 D3T3

考虑 $k=n$ 怎么做，先做 $a_i\leq b_i$ 的任务，这一部分按照 $a$ 升序排序，后面 $a_i>b_i$ 的按照 $b$ 降序排序，由 exchange argument 可以推出来。两部分是独立的，前面一部分肯定是贪心选前缀可以让起点最小。考虑后面一部分 $a_i$ 这个向量可能很大，需要 dp 求解。令 $f_{i,j}$ 表示前 $i$ 个选了 $j$ 个的最小起点，容易有转移：$f_{i,j}\leftarrow\min(f_{i-1,j},\max(f_{i-1,j-1}-b_i,0)+a_i)$。先考虑怎么合并答案，由于两个部分都是单调的，$ans_k=\min_{i+j=k}\max(af_i,bf_j-pre_i)$。经典拆 $\max$，跑个双指针就行了。不难猜测 $f_i$ 关于 $j$ 单调不降且下凸。考虑凸优化，优先队列维护所有相邻值的差分，重新考虑转移。对于最大的 $t$ 使得 $f_{i-1,t-1}\leq b_i$，注意到 $b$ 是有序的，那么 $t$ 也是单调的。

$j<t$ 因为 $f_{i-1,j}\leq b_i<a_i$，有 $f_{i,j}=f_{i-1,j}$。
$j=t$ 有 $f_{i,j}=\min(f_{i-1,j},a_i)$。
$j>t$ 有 $f_{i,j}=\min(f_{i-1,j},f_{i-1,j-1}+a_i-b_i)$。

为了统一形式，加入一个虚点 $f_{i-1,t-1}=b_i$。由于是下凸的，加入一个差分向量 $a_i-b_i$ 即可。时间复杂度 $O(n\log n)$。

原神模拟赛 D3T4

额外边构成链的做法就是维护 $t_{l,r,0/1,0/1}$ 表示当前 $l$ 连通块是否与 $0$ 连通，同理有 $r$，可以直接线段树维护。答案就是 $t_{1,n,1,1}$。考虑 $m$ 构成树之后，我们仍然希望刻画连通块，其实是好处理的，对于 kruskal 重构树的一个子树而言，内部的所有边我们可以称其为一个连通块，这个的一个前序遍历拿出来的话，一个连通块必定是一个区间，但是一个区间不一定是一个连通块。再想一下的话如果一个区间事实上不构成连通块时不会影响答案，因为额外边的控制范围不变。kruskal 跑出来等效链即可。时间复杂度 $O(n\log n)$。

QOJ2552

考虑钦定掉 $\max$，有 $a_x+a_y\ge b_x+b_y$ 等价于 $a_x-b_x\ge b_y-a_y$，对于 $a_x-b_x,b_y-a_y$ 作为下标插入点，线段树上维护 multiset，并且一个节点维护四种关系的答案即可，合并时只需要考虑跨区间的情况。时间复杂度 $O(n\log n)$。

CF1178F2

缩颜色段是显然的，如果缩完之后超过了 $2n$ 就显然无解。考虑区间 dp 求出 $f_{l,r}$ 表示 $[l,r]$ 染色的方案数，显然需要有最小值的出现区间被 $[l,r]$ 完全包含。记录所有区间位置，将每个小子段的 $f$ 乘上就行了。时间复杂度 $O(n^3)$。

AT5042

从 zr 偷的题。考虑先做 $n\leq 10$ 的部分分，也就是先确定所有树边的顺序，这是 $n!$ 的。那么对于一条非树边 $(u,v)$，其最小加边时间必定大于树上路径 $(u,v)$ 的时间的最大值。但这个不是计数，是求权值和，考虑倒序扫描线枚举当前位置填什么。这种东西经常要考虑灵活换顺序，可以从后往前填写，必须填完非树边再填树边，每个非树边限制就形如，加入该边之后才可以填写标号 $=x$ 的树边。那么将边抽象成一个点，就是一个 DAG 的限制图。$u\to v$ 表示边 $u$ 的边权必须在 $v$ 之前。那么就是一条右向链挂着一堆内向点，分别代表树边上的点以及限制挂在的节点上。直观想法就是倒序扫这个链，可以设计一个 dp，表示扫到了最后 $i$ 个边代表的点（$1\leq i\leq m$），其中已经加入了 $j$ 个非树边的点，树边对应的权值和为的方案数与和，分别设为方案数 $f_{i,j}$ 以及所有方案的贡献和 $s_{i,j}$。dp 的顺序是从后往前，先加非树边再加树边。显然非树边代表的点随便插入，树边点是重要的，只能插在当前序列的最前面。显然加入非树边点时有转移 $(i+1)f_{i,j}\to f_{i+1,j},(i+2)s_{i,j}\to s_{i+1,j}$。加入树边点时有转移 $f_{i,j}\to f_{i+1,j+1},s_{i,j}+(i+1)f_{i,j}\to s_{i+1,j+1}$。每时每刻有用的状态都只有 $1$ 个。连续加入 $k$ 个非树边点时贡献为 $f_{i,j}(i+k)^{\underline k}\to f_{i+k,j},s_{i,j}(i+k+1)^{\underline k}\to s_{i+k,j}$。可以做到 $O(n!\text{poly}(m,n))$。

考虑优化，显然是搞成状压的样子。注意到所有状态的瓶颈在于求出来第 $i$ 条树边代表的点上挂着多少个子节点，这个是 $a_i$ 的话执行那个 $k=a_i$ 的快速转移即可。对于后缀的树边进行状压，也就是维护 $w_S$ 表示后面有 $S$ 集合的边子问题中的四元组，也即方案数与贡献和。$c_S$ 表示 $S$ 点集导出子图的非树边边数，可以 $O(2^nn)$ 高维前缀和预处理，枚举 $S=T\cup\lbrace u\rbrace$，转移时就可以 $O(1)$ 查询 $a_i$，因此时间复杂度为 $O(n2^n)$。

P9340

显然一个连通块的根节点是区间内 $a$ 的 lca，容易求的。那么考虑容斥成所有 $a_i$ 到根的所有路径的并集，减去区间 lca 的深度。考虑怎么快速求 $a_i$ 到根的路径并，首先倒序离线扫描线 $a$ 的序列维 $l$，我们希望不重不漏计算贡献，并且靠前位置优先算贡献。直接使用颜色段均摊，扫描到 $l$ 时，直接将到祖先的链全部覆盖上颜色 $l$，询问路径并即为颜色在 $[l,r]$ 之中的点数。显然是对的。使用 ODT 维护，树链剖分拍成序列。时间复杂度 $O(n\log^2n)$。

不知名联考题

给出一棵 $n$ 个点的有根树。$q$ 次询问，每次给出 $l,r$，表示询问树上总共有多少个点，满足其子树包含 $[l,r]$ 中的至少一个点。$n\leq 5\times 10^5,q\leq 10^5$。

考虑拆出来 $u$ 对哪些询问有贡献，显然就是子树内所有数 $p_i$ 排序后跨过至少一个点的 $[l,r]$。这样显然太多了！其实可以只关心相邻的 $(p_i,p_{i+1})$ 的贡献，设 $p_0=0$，那么只需要对 $l\in[p_i,p_{i+1}),r\ge p_{i+1}$ 的做 $+1$ 的贡献即可。这是一个二维数点问题。考虑怎么找出来这些贡献点对，不难发现有继承以及合并子树带来的，所以本质不同的 $(p_i,p_{i+1})$ 是很少的，$+1$ 完全可以改成 $+k$，这样是更高效的。那么在合并子树时统计这些 $p_i,p_{i+1}$，用 std::set 可以高效找出来前驱后继，在此基础上使用启发式合并的复杂度就是正确的，而 $k$ 显然就是当前子树的深度，这个复杂度是 $O(n\log^2n)$，线段树合并的复杂度是 $O(n\log n)$。注意到二维数点中修改次数 $O(n\log n)=10^7$ 与查询次数 $q=10^5$ 严重不平衡，因此需要使用 $O(1)-O(\sqrt n)$ 的分块来平衡。时间复杂度 $O(n\log n+q\sqrt n)$ 或者 $O(n\log^2 n+q\sqrt n)$。

20241001

P7877

考虑建图描述操作，显然一个初始的连续段可以直接合并掉。注意到一个连续段的前驱都是确定的，并且后面的都移动完之后这个连续段才有可能移动。建立边 $u\to v$ 的意思就是必须要求 $v$ 在 $u$ 之前进行移动，那么一组拓扑序就是第一问的答案。如果图有环就是 NO。那么一个连续段 $[l,r]$ 需要建的边就是：对于本行右边的连续段连边，并且对于 $l-1$ 所在连续段右边的连续段连边。都可以只对最靠左的连就达成连通性限制了（后缀优化建图）。第二问就是有多少点可以到达 $u$，可以 bitset 维护。时间复杂度 $O(n^2/w)$。

P10037

先考虑如何刻画 $f(v)$。大小关系有点反直觉，改成 $a_i-b_i\ge 0$ 了哦。考虑做出来 $pre$ 表示 $b$ 的前缀和，那么就要求任意时刻 $a$ 都在 $b$ 之上。记录 $s_i=\max_{j\leq i}pre_j$，如果确定一个 $S$ 表示要保住 $S$，判定 $S$ 是否可行。显然必须有 $s_{dep_{S_i}}\leq 0$，并且最终 $S_i$ 存活要求分到了 $a_{S_i}=s_t$。以上两点是充分必要的。形式化地：

构造 $p_i=p_{i-1}+v_i,s_i=\max(s_{i-1},p_i)$。
若 $s_t=0$，$f(v)=n$。否则记录有 $q$ 个点满足 $s_{dep_i}=0$，答案为 $\min(\lfloor\dfrac{k}{s_t}\rfloor,q)$。

因为树的形态不变，所以 $cnt_i$ 表示深度 $=i$ 的点是不变的。下标最大只关心到 $t+1$。前缀和折线是经典的倒序 dp 模型，但我们需要求出首次 $>0$ 的位置。因此两部分拆开做，分别为 $f_{i,j}$ 表示首次 $>0$ 的位置在 $i$，在 $i$ 的位置和为 $0<j\leq m$，$g_{i,j}$ 表示倒着做了 $i$ 个，前缀和最大值为 $j$ 的方案数。这两个都是容易前缀和优化 dp 做到 $O(mt^2)$ 的。

把 $s_t=0$ 的提前计入答案，然后枚举 $p$ 表示深度 $\leq p$ 的，即在 $p$ 时刻前缀和 $>0$，此时和为 $x$，枚举后面的和 $y$，方案数是类似卷积的东西，但是贡献为 $\min(cnt_p,\lfloor\dfrac{k}{x+y}\rfloor)$，注意到 $k$ 很小，直接对于 $k$ 跑整除分块即可。时间复杂度 $O(mt(t+\sqrt k)+n)$。

P6729

不难发现答案具有单调性，也就是一段前缀的 $ans$ 是不合法的，观察大样例可得 $\Delta ans\leq 1$，不难发现是对的。那么现在就是一个判定较少的可行性问题，对于当前答案 $ans$，考虑将 $w_u\leq ans$ 的全部扔到 $C$ 外面，只需要考虑 $w_u>ans$ 的个数是否大于 $ans$。那么先将 $ans\to ans-1$，然后判定是否可以取到 $ans$，再判定是否可以取到 $ans+1$。那么维护当前 $w_u>ans$ 的集合，每次要求取出 $w=ans$ 的数量 $f(x)=\sum [w_i=x]$。树链剖分后，对于 $w$ 的更新就形如 $u$ 到祖先链的 $O(\log n)$ 段区间加 $1$ 或 $-1$。这个东西很好用分块维护，维护每个块值为 $x$ 的个数，散块暴力重构，整块直接打标记。时间复杂度 $O(q\sqrt{n\log n})$。

AT_abc216_h

考虑让时间也加入，就是给定一堆起点 $(0,x_i)$，若当前在 $(x,y)$ 就可以走到 $(x+1,y-1)$ 或者 $(x+1,y)$。计数的就是有多少条点不相交的路径组。枚举最后每个波特的位置 $y_1,y_2,\cdots,y_k$，直接上 LGV 引理，答案即为：

\[\sum_{y_1,y_2,\cdots,y_k}\sum_{p}(-1)^{\sigma (p)}\prod_{i=1}^k\binom{n}{y_{p_i}-x_i} \]

对这个式子进行 dp 即可。具体而言，维护 $f_{i,S}$ 表示考虑到了数轴前 $i$ 的位置，确定下来了 $y_{p_i}$ 的波特集合是 $S$，这些 $y$ 都 $\leq i$，此时的贡献和。转移枚举是否存在一个点取到 $y_{p_j}=i$，而考虑将 $\sigma (p)$ 拆到每个位置上，就是 $c_i$ 表示前面大于 $i$ 的个数，贡献就是所有 $(-1)^{c_i}$ 的乘积。枚举这个 $i$ 时可以同时计算一下 $c_i$，此时转移是容易的。时间复杂度 $O(nk2^k)$。

原神模拟赛 D1T4

AC 自动机维护一下非法路径的失配情况。有效边数是显然不足 $O(n^2)$ 的，所以我们显然不能直接暴力建，需要更改一下与本身出边不同的情况，拿可持久化修改一下就好了。之后直接在 AC 自动机上跑一下最短路即可。时间复杂度 $O(m\log m)$。

ARC184E

思想：对于等价类找到代表元。

这不是我们 [集训队互测 2022] 线段树吗。考虑 $f(A,B)$ 就是 $B$ 做 $k$ 阶差分得到 $A$ 的最小 $k$。前缀和太难看了，那么考虑 $B$ 做 $k$ 阶差分事实上就是在考虑一个网格图。对于任意时刻的 $B_i$，必然由若干个 $j\leq i$ 的 $B_j$ 异或而来。考虑一张网格图，点 $(x,y)$ 表示第 $x$ 个版本第 $y$ 个位置。令一次修改为创建一个新版本，一条有向边代表新版本的值会由这个点异或而来。首先要继承，任意 $(c,i)$ 必然对 $(c+1,i)$ 有边，而一操作就相当于，令当前版本为 $c$，对所有 $l\leq i<r$ 的 $(c,i)$，连边 $(c,i)\to (c+1,i+1)$。重新考虑 $B_i$ 由哪些异或而来。显然当且仅当 $(0,j)\to (c,i)$ 有奇数条路径时，$B_i$ 会异或上 $B_j$。这个显然就是 $\binom{c}{i-j}\bmod 2$，由 lucas 定理，当且仅当 $(i-j)\subseteq c$ 时取 $1$。事实上这个东西可以生成函数，也就是考虑 $(1-x)^kF$。注意到 $c$ 一定时是有周期的，那么如果可以相互转换，先称之为是一个等价类，差分就相当于是在一个环上走，那么考虑对每个等价类选取一个代表元，求出一个数列到代表元的距离 $p_i$，答案即为 $(p_i-p_j)\bmod m$。判定等价类可以对代表元使用哈希。那么考虑选取代表元的问题，直接通过上述操作从小到大跑 $2^k$ 表示是否要移位 $2^k$ 次。判定是否字典序会变小，最终可以变换到 $a'$ 上，同时求出了距离 $p$，环长根据 lucas 定理那个就是最小的 $2^t$ 使得 $2^t+fir>m$。其中 $fir$ 为首个不为 $0$ 的位置，最终问题形如 $\sum_{i,j}(p_i-p_j)\bmod m$，容易用树状数组解决。时间复杂度 $O(nm\log nm)$。

卡哈希也是真没素质。

ARC183E

和 QOJ9252 差不多啊。注意到每次操作是交换相邻的，那么一个点最多可以到达的也是一个区间 $[l_i,r_i]$。也就是该区间内的 $b_j$ 都在 $a_i$ 的子树内，容易二分求出。但并不是所有方案都是理想的。观察 $[l_i,r_i]$ 的结构一定是，仅包含与相离。这种结构经典处理方式就是建树，父亲即为第一个包含它的区间。而实际上能走到的 $[L_i,R_i]$ 一定就是由此收缩而成。那么考虑什么时候一个点是定死的，$l_i=r_i=i$ 是一个充分条件，考虑拓展：如果一个区间完全包含了 $k$ 个区间，并且 $R_i-L_i+1=k$，就一定满足这个 $[L_i,R_i]$ 一定是内部点的一个排列，不允许外面的点加入。把这堆区间扣掉之后求剩余区间长度乘积即可，注意要去重，因此要记录等价类大小，在最后除掉。时间复杂度 $O(n\log n)$。

QOJ2562

考虑 $f_{u,i,j}$ 表示 $u$ 子树内断了 $i$ 条边，当前 $u$ 连通块权值和为 $j$ 是否可行，瓶颈在于 $j$ 完全无法记录。从和要求在 $[L,R]$ 入手，先考虑定义域值域互换，我们希望记录一些合法的值来推知一个状态是否合法。令当前 $u$ 所在的连通块大小有 $x,y,z$ 三种选择，则 $x<y<z,z-x\leq R-L+1$ 时，$y$ 是没有用的，不然选择 $y$ 时都可以调整到 $x$ 或者 $z$。注意到已经割出来的连通块总和在 $[iL,iR]$ 之中，因此 $j$ 的值域 $O(k)$，极差 $\leq i(R-L)$，时间复杂度 $O(nk^3)$。

CF2018E2

显然对于条件 $2$ 的转化就是一堆有公共点的线段集必然在同一个子集。最终要求的是 $k$ 个子集，每个子集大小为 $m$，要求出 $mk$ 的最大值。注意到对于给定的 $m$ 可行的 $k$ 是一段前缀，记录这个最大的 $k$ 是 $f(m)$。用 P9132 的套路，对 $m$ 根号分治，在 $m$ 很大时是平缓的。我们希望实现一个函数 $f(x)$ 表示要求分出来大小均为 $x$ 时最多有多少个子集。对于 $m\leq B$ 的直接暴力跑 $f(i,+\infty)$，对于 $m>B$ 反过来去二分出来 $f(x)=i$ 的极长区间 $[l,r]$。时间复杂度为 $O(T(n)(Bn+\dfrac{n^2\log n}{B}))$，其中 $T(n)$ 为实现 $f(x,y)$ 的复杂度。那么这个就是 $B=\sqrt {n\log n}$ 时取到 $O(T(n)\sqrt {n\log n})$。现在思考如何实现 $T(n)$，显然考虑 dp。刻画 $T(n)$ 的方法应为区间的划分。E1 就是线性 dp 的状态，转移形如 $f_i\leftarrow f_{j-1}+1$，而这个 $j$ 可以线段树找到公共点覆盖 $k$ 次的点，容易做到 $T(n)=O(n\log n)$，总复杂度是 $O((n\log n)^{1.5})$，过不去 E2。考虑让端点不重复，用区间交集来刻画。维护每个位置的覆盖次数 $cnt$，就需要维护 $cnt$ 的后缀 $\max$ 序列 $suf$。注意到区间不交，那么 $|suf_i-suf_{i+1}|\leq 1$，就可以去维护 $suf$ 的差分 $c_i\in\lbrace0,1\rbrace$。往后插入 $r$ 时，$c$ 的变化就是区间覆盖 $0$。用并查集维护所有的 $10000$ 状物，可以让 $T(n)=O(n\alpha (n))$。不过写整体二分 dp 是真神了，由中间说的那堆东西，$f$ 只会跑 $O(\sqrt n)$ 次。时间复杂度 $O(n\sqrt n\alpha(n))$。

20241002

想到反转 dp 了认为贡献会重复没敢写，$400\to 345$。/tx。

20241003

P11146

只考虑 $a_i\neq b_i$ 的位置，仍然考虑按位对前缀贪心。每次操作形如对一个区间内的取反。考虑怎么判定是否可以对当前点进行取反。用类似 WC2024T3 的方法，建图的方法来描述这些操作，$l\to r+1$ 作为边，那么一次可以操作的 $[l,p)$ 使得仅对 $[l,p)$ 有取反作用的就是在同一个连通块里的 $p$。直接贪心取出来最大的可达的 $p$，如果 $l\ge p$ 就寄了，否则就对 $[l,p)$ 都进行一次取反。如果后面有覆盖，对应的原操作序列无非就是异或一下路径上对应的操作是否执行。用 BIT 模拟上述过程，时间复杂度 $O(n\log n)$。

QOJ8047

考虑判定一个 dfs 序是否合法。维护到现在 $1\to p_{i-1}$ 的链，弹出 $>p_i$ 的部分之后，在当前的栈顶的下一个节点后面（为了满足一个 dfs 序按照递增顺序遍历的限制）接上 $p_i$ 作为子节点，如果栈弹到空了就是不合法的。容易发现这样的构造过程与一棵树形成了双射。这样的贪心必须要求一个树的构造是对应一个排列的，我们希望对满足某些条件的树计数。那么对于一个合法的树，我们要求其不可以更换顺序，也就是说一个儿子不能被接到别的上去。对于一个 $u$，其儿子都是升序的，对于两个相邻的节点 $a,b$，其中 $a$ 在前面，必须满足 $a$ 不为叶子（不然 $b$ 可以直接接上去），并且 $a$ 的最大儿子为 $c$ 时，必须有 $c>b$，不然 $b$ 接在 $a$ 下面是等效的。

考虑给定树的形态之后怎么计算标号方案，可以连成 DAG 计算拓扑序。$u\to v$ 形如 $u$ 的标号必须 $<v$ 的标号。那么就是 $\text{firstson}(u)\to u$，所有相邻儿子连边，以及 $c\to b$。考虑让它变成内向树，内向树反图的拓扑序是简单的。考虑容斥，强制让某条边不满足，就让 $c\to b$ 是不满足的，那么可以反向成 $b\to c$，此时 $a\to b$ 就是没用的，这样可以变成内向树。dp 就是，大小为 $i$ 的树，最后一个儿子额外挂了个大小为 $j$ 的子树，此时前面 $i$ 个点的贡献和。转移枚举首个儿子子树大小即可。答案就是 $f_{n,0}(n-1)!$。时间复杂度 $O(n^3)$。

P7619

弱智题，注意到瓶颈在于求 $\sum t_j(n-j+1)$，这个东西最小显然要让 $t$ 不降。$t\leq 10^5$ 的话直接上权值线段树，维护每个值的排名，形如区间加。一个区间的贡献也是容易维护的。在线维护每个数比它小的个数以及和。容易做到 $O(n\log V)$。

P6371

数位 dp，显然容斥成 $\leq B$ 减去 $\leq A-1$，考虑对于 $x$ 整除这件事。拆位，每一位上有若干可选，同时受 $10^i$ 的影响，相当于每个位置必须选一种重量的物品，最后要求模 $x$ 意义下为 $0$。这个东西尽管很多，但是对 $x$ 根号分治就行了，$x\leq T$ 时种类只有 $O(T)$，是简单的，对于 $x>T$ 直接暴力就行了。弱智题不想写了。这东西实现可以用记搜，好写。

P7862

首先二分答案。注意到 $k$ 小爆了，而一个连通块有多于 $k$ 个数时一定可以凑出来模 $k$ 为 $0$ 的。因此判定一个连通块时，背包复杂度是 $O(k^2)$ 的。令检查的为 $mid^2$，二分时就考虑对横轴扫描线，如果存在 $mid\times mid$ 的矩形中有大于 $4k$ 个点，那么 $mid$ 一定是合法的。std::set 维护当前点，优化建图一下就可以求出所有的连通块。时间复杂度 $O(nk\log V)$。

20241004

P11160

01-trie，低位向高位建。对于 trie 数整体 $+x$，可以采用以下方法：下放标记时，如果 $2\mid x$，直接向两侧下放 $x/2$，否则交换左右子树并且向 $0$ 下放 $(x+1)/2$，向 $1$ 下放 $(x-1)/2$。对于一个子树加，直接暴力分离并且暴力合并。时间复杂度分析类似于线段树合并，时间复杂度 $O(n\log V)$。

P7450

每个数的颜色在 $[1,k]$ 之间时有显然的斯坦纳树上 dp 的做法，复杂度 $O(n3^k+2^kn\log n)$。这个 dp 在【20240910】QOJ5175 中讲过了，分别为枚举子集以及最短路的三角形不等式。运用 CF2003F 的套路，使用 color-coding。考虑在颜色种类数很大时，随机映射到 $[1,k]$ 上，单次的正确率为 $\dfrac{k!}{k^k}=0.038$。做 $T=200$ 次就会有足够小的概率得出错误的解。

P7929

基环树常用思想就是断环成树，那么随便找一条环边给它断成树，并同时记录这边上两个点的颜色状态即可。跑 $3$ 次，每个 dp 都设计成 $f_{u,0/1,0/1}$ 分别表示 $u$ 子树内，$u$ 的颜色是 $0/1$，$u$ 的儿子中有 $1$ 还是 $u$ 的父亲为 $1$，使得 $u$ 子树内点全部合法的最小代价。转移是显然的。时间复杂度 $O(n)$。

P11106

考虑对于前缀维护当前 $q,r$ 的两个值域区间 $[x_q,y_q],[x_r,y_r]$。每次加入 $p$ 若产生贡献，显然对两个的影响分别是更新 $y_q$ 或 $x_r$。那么如果在加入 $p$ 后，两个的值域区间产生了交集。那么后缀的最长上升与最长下降都可以计入答案，这些未被选取的一定不会影响答案，并且两个子序列是独立的。那么枚举这个产生交集的位置，后面的贡献是容易维护的，考虑最大化前面的贡献。注意到两个区间无交，那么对于每个位置，前缀的所有值，一定是 $<\text{last}(a_i)$ 的都放到 $q$，$>\text{next}(a_i)$ 的都放到 $r$，这样做一定是不劣的。考虑 $a$ 放在 $q$ 还是 $r$，那么前驱后继的贡献是确定的。在前缀这样的贡献可以最大，后缀这样的贡献也最大。对于值域一段前缀的最长下降以及一段后缀的最长上升都是容易用 BIT 维护的。倒序扫描线维护这个东西，时间复杂度 $O(n\log n)$。

P10694

弱智题，乘法分配律掉两个串的影响。答案拆到每个子序列上统计即可。也就是考虑一个子序列的端点为 $l_1,r_1$，另一个子序列端点是 $l_2,r_2$，贡献即为 $\min(l_1,l_2)(n-\max(r_1,r_2)+1)$。发现对于一个前缀，$s_1$ 匹配到 $j$，$s_2$ 匹配到 $k$ 的子序列对数的 $\min(l_1,l_2)$ 求和是可以接受的。直接进行 dp 即可。时间复杂度 $O(nm_1m_2)$。

20241005

你猜为什么今天没了。

20241006

联考 L42

显然要将用乘法分配律贡献拆掉，那么就是每个点集中选取恰好一个点给出 $a_v$ 的贡献。使用 dp 来做，那么一个观察就是我们当前的状态只需要记录没有选入任何点集的点的状态，也就是对于子树 $u$，令 $f_{u,i,j}$ 表示在其中有 $i$ 个未匹配的点系数为 $a_v$，剩下 $j$ 个未匹配的点系数为 $1$。那么观察每个合法的 $V'$ 就是一个根挂着一堆叶子，如果 $u$ 是根，每个子树可以选择至多一个点合并上来。如果 $u$ 是叶子，直接继承所有子树的贡献。前面一维复杂度是树上背包，时间复杂度 $O(n^4)$。

QOJ3998

比较套路的题。总结：类似于图连通性的维护，这类不可撤销贡献的问题可以使用整体二分巧妙地控制住整体的插入次数。

注意到求出所有的 $f(i)$ 必须使用背包。这是一个 $(\max,+)$ 的过程，明显是无法撤销的。而背包的大小是 $k$，所以我们要控制插入的次数，与 $n$ 有关。注意到对于一个给定的 $l$，合法的 $r$ 是一段后缀。所以可以考虑整体二分，递归 $\text{solve}(l,r,x,y)$ 表示 $ans_{l,r}\in[x,y]$。注意到这种背包需要维护一个全局的，我们可以在刚进入函数时维护好除了 $[l,r]\cup[x,y]$ 的所有位置的背包，并且求出 $\text{mid}=(l+r)/2$ 位置的 $ans$。考虑这个 $ans$ 怎么求，可以对于这个内部进行二分答案。在二分答案的过程中加入已经确定部分的位置的背包，可以对于 $[x,y]$ 线性插入次数。此时求出 $ans$ 后，加入 $[pos,y]\cup[\text{mid},\min(r,x-1)]$ 位置的背包，向左递归求 $\text{solve}(l,\text{mid}-1,x,pos)$，向右时恢复到递归前的背包状态再加入对应的位置。时间复杂度 $T(n)=2T(n/2)+O(nk)$，总共是 $O(nk\log n)$。

ZR2964

注意到 $k=2$ 的部分分就是标记 $x,y$ 的路径中点 $t$ 对应的 $O(1)$ 个 dfs 序区间。那么 $k>2$ 时事实上只需要要求其对 $k-1$ 对关键点的距离都相同，取出这 $k-1$ 对，求出所有 dfs 序的交即可。

ZR2965

形态是树一定不劣，考虑给定是树时直接 dp 即可，维护 $f(u,0/1/2)$ 表示 $u$ 子树内，$u$ 选入独立集，$u$ 不选入独立集且是否有儿子被选的方案数。容易做到 $O(m)$ 求出单个树的答案。考虑整体直接爆搜出所有的树，本质不同即不同构的无根树，在 $\leq 21$ 个点时很少，只有不超过 $5\times 10^6$ 个。那么考虑怎么爆搜：钦定重心为根，枚举往下的划分，用树哈希判重，可以一定程度优化爆搜的时间。

20241007

P10868

拆贡献的话，发现每个点的贡献系数 $k$ 仅与 $i$ 有关，先列出来一个暴力 dp 表示前面有 $i$ 个点后面有 $j$ 个点的贡献系数为 $f_{i,j}$，转移是容易的。再令 $g_{i,j}=(i+j)!f_{i,j}$，发现转移就是网格图 $(1,1)\to (i,j)$ 的路径乘积求和。可以直接预处理 $\prod (i-\dfrac{1}{2})$ 以及组合数做到 $O(n)$。

P11134

直接上 boruvka 算法，每次就是要找向外边权且不在同一连通块的最小边。首先可以把 $l,r$ 给离散化掉。那么就是询问在 $[l_i,r_i]$ 有交的线段内 $a_i+a_j+|b_i-b_j|$ 的最小值，以及不与该最小值同一颜色的次小值。首先将绝对值拆了，就是按照 $b$ 对于所有点进行排序，先求出 $b_i\leq b_j$ 的最小值，再求出 $b_i\ge b_j$ 的最小值。那么每次只需要维护 $a_j+b_j$ 或者 $a_j-b_j$ 的最小值以及次小值。那么每次就形如询问一段区间有交的信息，是容易用线段树维护的。使用标记永久化可以降低常数，时间复杂度 $O(n\log^2 n)$。

P7143

得益于线段树优美的分治结构，考虑直接使用记忆化搜索加分治解决这个问题，每次就是选取 $mid$ 进行分治。并且由于这是标准线段树，我们只关心它的长度，可以直接维护 $ans_x$ 表示 $n=x$ 时的答案，以及前后缀跨儿子的情况，也就是记 $suf_x$ 表示所有以 $x$ 结尾的后缀的 $cover$ 的和，同理有 $pre_x$。可以快速合并。时间复杂度 $O(T\log n)$。

联考 L43

自己推出来了，但是懒得写了，贺一发。

考虑对于每个点对 $(a,b)$ 算出有多少对 $(i,j)$ 途径了这个状态。从 $(a,b)$ 倒推。其可以到达两个状态 $(a,a+b)$ 和 $(a+b,b)$。构成了一个树形结构。考虑将中间相同的元素缩起来，可以看作一个序列。一开始是 $(a,b)$，后来是 $(a,a+b,b)$。每一轮在两个数中间插入它们的和。

在每次新加入的位置统计贡献，那么所求即为：这个过程不断持续下去，得到的序列中 $\le n$ 的数的个数。观察一下得到的序列。我们可以把每个数表示为 $(x,y)=ax+by$。得到如下性质：任意时刻，对于两个相邻的数 $(a,b),(c,d)$ 有 $ad-bc=1$。所有满足 $ad-bc=1$ 的非负整数 $a,b,c,d$ 都会出现在序列中。由裴蜀定理，我们可以得到：所有满足 $\gcd(i,j)=1$ 的 $i,j$，$ai+bj$ 都会出现在序列中。

所以答案即为 $g(n,a,b)=\sum_{i=1}^{n}\sum_{j=1}^n[\gcd(i,j)=1][ai+bj\le n]$。

所求即为 $f(n)=\sum_{i=1}^n\sum_{j=1}^ng(n,i,j)$。

考虑莫比乌斯反演。设 $G(n,a,b)=\sum_{i=1}^{n}\sum_{j=1}^n[ai+bj\le n]=\sum_{i=1}^n\lfloor\frac{n-ai}{b}\rfloor$。则 $g(n,a,b)=\sum_{i=1}^n\mu(i)G(\lfloor\frac{n}{i}\rfloor, a, b)$。

$f(n)=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\mu(k)G(\lfloor\frac{n}{k}\rfloor, i, j)$。

$f(n)=\sum_{k=1}^n\mu(k)\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor}G(\lfloor\frac{n}{k}\rfloor,i,j)$。

设 $F(n)=\sum_{i=1}^n\sum_{j=1}^nG(n,i,j)$。

展开，$F(n)=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\lfloor\frac{n-ki}{j}\rfloor=\sum_{k=1}^n\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}s(n-ki)$。其中 $s(i)$ 表示 $1\sim i$ 的因子数之和。

使用数论分块计算即可，时间复杂度 $O(n\log n)$。

联考 L46

记 $m=\sum a$ 与 $n$ 同阶。无解的一个充分条件是出现 $i<j<k$ 使得 $a_i>a_j>a_k$，其实这个也是必要的。也就是说有解当且仅当最长下降子序列的长度不超过 $2$。由 Dilworth 定理（最小链覆盖 $=$ 最长反链）也可推知这点。~~这不是我们【NOI2018】冒泡排序吗。~~ 考虑 dp，从小到大填数是有救的。观察合法序列的结构，如果不是前缀最大值，那么这些剩下来的位置一定递增。扫描线值域，当前扫到了 $x$，不难发现如果首个值为 $x$ 插在中间的话，后面的部分都会成为非前缀最大值，所以这一部分是必须不降的。而从左往右填时一个位置要么是前缀最大值要么是当前最小值。考虑 dp，$f_i$ 表示第一个非前缀最大值位置出现在 $i$ 即可。转移就枚举最后接了多少个 $x$，每次形如对 $f$ 后缀和更新，时间复杂度 $O(nm)$。

联考 L47

这个就是对 $y$ 整除分块，形如 $O(n\sqrt n)$ 次查询一个单点的前驱与后继，$O(n)$ 次区间覆盖。那么可以使用分块平衡，用较大的时间复杂度处理修改，就是可以对整块维护块间前驱后继，以及块内的直接后继。时间复杂度 $O(n\sqrt n)$。

THUSC2024 D1T3

首先考虑二分答案 $mid$，判定是否可以让所有链的长度 $\leq mid$。然后 dp 做：$f_u$ 表示 $(u,fa_u)$ 所在链向上传递的最短长度，$g_u$ 表示 $(u,fa_u)$ 所在链向下传递的最短长度。如果 $>mid$ 就寄了。现在在考虑 $u$ 的话，就相当于每个子节点有 $f,g$ 可选。那么以 $f_u$ 为例，假设集合 $S$ 中的子节点选取了 $f$，那么就要求 $f_x+g_y\leq mid,x\in S,y\notin y$ 的前提下最小化 $\min_{i\in S}f_i$。那么考虑将所有子节点的 $f,g$ 拉出来排序一下，扫描线一下 $f$ 的最大值 $mx$，将 $\leq mx$ 的都设置成选 $f$，随便维护一下还在外面的 $g$，是不是没了啊？？？时间复杂度 $O(n\log n\log V)$。

U285763

显然要枚举 $n$，我们希望在与 $\lg m$ 有关的复杂度内完成统计。那么考虑怎么统计 LCS：将 $n$ 的所有子串视为模板串，将 $m$ 视为一个匹配字符串的过程，在此过程中记录最长匹配长度。注意到 $n$ 的长度只有 $4$，考虑直接对于 $n$ 构建一个自动机，即往后接一个数字 $c$ 时可以转移到哪里的。这一步可以 AC 自动机，但没必要，可以直接拿 map 暴力维护。而在一个自动机节点上时就已经有了当前匹配的信息。并且在数位 dp 时，我们可以直接记录当前在哪个节点。也就是记录一个状态 $f_{i,j,k,0/1,0/1}$ 表示当前考虑了 $m$ 最高的 $i$ 位，当前匹配到了自动机 $j$ 号节点，历史最大的匹配长度是 $k$，当前的数 $x$ 是否与 $m$ 的最高 $i$ 位完全一致，$x$ 是否只由前导零构成，的方案数。答案就是 $\sum jf_{i,j,k,0/1,0}$。由于自动机大小最多为 $k=10$，时间复杂度上界 $O(nk|\Sigma|\lg m)$，本题中 $|\Sigma |=10$ 表示十进制数位种类数。

20241008

CF578D

考虑直接 dp 套 dp，先考虑怎么求两个字符串的 LCS，显然就是 $f_{i,j}=\max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+[a_i=b_j])$。这个题可以直接 dp 时考虑把这三个东西扔进内层状态，注意到 LCS 长度需要为 $n-1$，那么转移时的 $f_{i,j}$ 有效必须满足 $|\min(i,j)-f_{i,j}|\leq 1$。直接将三个量扔进 dp 状态里。即设 $g_{i,x,y,z}$ 表示有多少个 $T[1:i]$ 使得对于 $S[1:i]$ 有 $g_{i-1,i}=i-x,g_{i,i-1}=i-y,g_{i-1,i-1}=i-z$，其中 $x\in\lbrace0,1\rbrace,y\in\lbrace0,1\rbrace,z\in\lbrace1,2\rbrace$，内层自动机大小为 $k=8$，转移可以做到 $O(nk)$。事实上容斥做法也是很好的。注意到只需要做一下去重即可，这样的复杂度是 $O(n)$。

becoder D4T1

首先判定无解：排序后相邻差 $>A$ 就寄了。考虑确认答案的结构：显然是不存在【相交但不包含】的结构；并且包含的嵌套不会超过 $2$ 层。证明都是考虑交换不劣。那么每段的结构都形如划分成 $[l,r]$，其中 $l,r$ 异奇偶配对，内层的 $(l,r)$ 相邻配对。容易使用树状数组优化到 $O(n\log n)$。

becoder D4T2

显然可以二分答案，我们直接关心从一个可以开始的状态能抵达的所有状态是否可以覆盖所有的店。之后直接从一个可以出发的点开始 bfs，每次模拟右下角的移动，可以使用差分维护出每一行的覆盖状态。最后直接判断是否把全部的都覆盖了即可。时间复杂度 $O(S\log S)$。

becoder D4.5T4

考虑将问题转化为选出一个尽量长的子序列，这个子序列的连续段数量 $\leq m+1$，长度作为 $ans_m$。记录每个连续段长度为 $a_i$，一个极长连续段内一定不会被断开。并且令划分出的 $m$ 个子段中允许空序列，这不影响答案。连续段数量 $\leq 2$ 是平凡的，假设形成了 $m$ 个连续段，那么 $ans_{\ge m-1}$ 一定都是 $n$。所以我们只会保留若干个连续段，容易发现删掉相邻两个连续段一定劣于删掉其中一个。所以删掉的连续段不相邻。两端的连续段代价都是 $1$，需要特殊考虑是否保留，中间的删除代价都是 $2$，枚举两端的 $4$ 种情况，问题转化为中间选择一些两两不相邻的连续段删去，使得总和最小。这是经典的反悔贪心问题，考虑当前最小的，要么选它，要么调整成选两端的。使用小根堆维护之。时间复杂度 $O(n\log n)$。

CF372C

什么？单调队列优化 dp？复杂度 $O(nm)$，这个不配有分的。

显然需要最小化 $\sum|a_i-x|$。考虑 dp，动态维护 $f(x)$ 表示当前在 $x$ 位置的最小代价。那么每次操作形如给 $f(x)$ 加上 $y=|x-x_0|$，以及对于每个 $x$ 对所有 $i\in[x-d\Delta t,x+d\Delta t]$ 的 $f(i)$ 同时取 $\min$。考虑使用 slope trick 来维护断点。每次区间加一次函数必然形成一个凸函数。注意到如果没有取 $\min$ 操作，斜率的变化一定是连续的。而取 $\min$ 操作事实上就是平移 $d\Delta t$，中间多了一段斜率为 $0$ 的平段。那么根据这个凸函数的形态，拿一个堆是很好维护断点的，分别维护所有断点 $i$ 使得 $|k_{i-1,i}-k_{i,i+1}|=1$，对于负和正的变化斜率分别维护，同时记录全局加的 tag 用来支持平移，以及 $x_0$ 为首个斜率变化点。记左边的段是 $l$，右边的是 $r$，每次考虑加入 $a_i$ 与 $[l,r]$ 的关系即可维护。时间复杂度 $O(m\log m)$。实现上用两个 multiset 维护即可。

CF888F

断环成链，考虑如何刻画相交这个条件，显然就是将一条边看成区间 $[u,v]$，不存在 $l_1<l_2<r_1<r_2$。区间 dp 的时候设一下 $f_{l,r,0/1}$ 使得 $[l,r]$ 连通且是否连了边 $l\to r$ 的方案数即可。转移时注意去重，时间复杂度 $O(n^3)$。

CF2021E3

正难则反的思想，考虑能节省多少，从 $k$ 小推到 $k$ 大。

考虑建立 kruskal 重构树，那么一个路径的最小的最大值就是两点 $\text{lca}$ 的点权。那么就是给定 $p$ 个叶子节点作为关键点，那么就是要选择 $k$ 个额外点。每个关键点找一个额外点最小化 $\text{lca}$ 点权和。可以直接在树上 dp，暴力的状态是 $f_{u,i}$ 为，仅考虑 $u$ 代表的连通块，$u$ 子树内选了 $i$ 个额外点的答案。这个重构树的性质是，任意点到根的路径上的 $w_i$ 是递增的，其中 $w_u$ 表示非叶节点 $u$ 的点权。维护 $\text{size}(u)$ 表示 $u$ 子树内的关键点个数。转移有三种，分别是做 $(\min,+)$ 卷积或者 $f_{rs,i}+\text{size}(ls)w_u$，右边同理。时间复杂度 $O(n^2)$ 可以通过 E2。考虑后面那个并没什么用，与 $rs$ 无关，也就是赋值 $f_{u,0}=w_{fa(u)}\text{size}(u)$。那么正常做 $(\min,+)$ 卷积就行。感性理解，每次能优化的越来越少，是一个凸的。理想情况直接闵可夫斯基和合并。所以直接维护 $f_{u,i}-f_{u,i+1}$，使用 std::set 启发式合并即可。时间复杂度 $O(n\log^2n)$。更优美的写法是，考虑平凡情况都是 $u$ 子树内经由 $fa(u)$ 进到相邻的那个儿子，维护一个 dp 表示能优化的最大值。递归地考虑往下放，考虑放在哪个点上，事实上就是一个选两者 dp 较大值往下走到叶子的过程，类似于链剖分可以直接维护。

P8859

考虑 $typ=1$ 就是前缀最大值的数量为 $n-k$，原因是对一个非前缀最大值是必须要操作的。直接 dp 表示 $f_{i,j}$ 填入 $\ge i$ 的数，非前缀最大值的个数是 $j$ 的方案数，考虑向后转移，枚举 $i-1$ 的位置，那么当且仅当 $i-1$ 填在最前面时会转移到 $f_{i-1,j}$，否则乘上 $(n-i+1)$ 就可以转移到 $f_{i-1,j-1}$。对于 $typ=2$，序列的部分分提示我们 $n$ 是一定不会动的，所以考虑断环成链，最后一个一定是 $n$。但是我们要求，从某个位置开始的序列的 $f(A)$ 的 $\min$ 恰好为 $k$。考虑对这些环排列找一些不变的性质：如何刻画在某个位置断环成链后的前缀最大值的数量的最大值。我们考虑用图论描述这个问题。把这些前缀最大值的位置单独拿出来一定是递增的，且保持一定的原来相对顺序，因此想到对于每个 $u$ 在环上顺时针沿着当前方向找最近的 $v$ 使得 $a_v>a_u$，连有向边 $u\to v$，注意到 $n$ 是没有出边的。因而这个 $f(A)$ 就是这个内向树的高度。将 $n$ 放在最后，考虑用 dp 维护这个事情。我们声称一个合法的树与一个环排列是双射，树根是 $n$，必须有父亲标号小于儿子。环排列的数量是 $(n-1)!$ 个，而一个环排列导出的树两两不同，而合法的树数量是 $(n-1)!$ 个（对于 $1\leq i<n$，其父亲有 $n-i$ 种选法），因此我们只需要对这样合法的树，高度 $=n-k$ 的树计数即可。转移考虑一个高度 $\leq i$ 的方案数即可，也就是前缀和优化。时间复杂度 $O(n^3)$。

20241009

becoder D4T3

注意到 $B$ 的定义中带绝对值是无法接受的，考虑用完美匹配来刻画一个排列，对于一个序列 $\texttt{1 1 2 2 }\cdots\texttt{n-1 n-1 n n}$，前面的表示位置，后面的表示值。考虑它的一组完美匹配，显然与原序列形成双射，那么 $\sum |i-p_i|$ 就可以刻画为作为匹配右边的数之和减去作为匹配左边的数之和。这样做就拆掉了 $|i-p_i|$ 的绝对值。考虑 $typ=0$ 的计数：直接对于这个长度为 $2n$ 的序列进行 dp 计数：$f_{i,j,k}$ 表示长度为 $i$ 的前缀，完成了 $j$ 对配对，现在所有数的贡献和为 $k$ 的方案数即可。转移考虑 $i$ 作为一个后面的还是作为前面的（待定，当前没有匹配）。注意到 $i,j$ 的信息已经足够转移的，这样计数的复杂度是 $O(n^4)$。确定字典序第 $s$ 小也是容易的，在前缀的基础上枚举当前位置的值，如果对应的合法序列的字典序区间 $[l,r]$ 覆盖了 $s$ 就确定了这个位置的值。时间复杂度 $O(n^6)$。

CF599E

考虑直接状压 dp，维护 $f_{i,S}$ 为 $i$ 作为根时其子树内有 $S$ 集合的点的方案数。每次形如对 $f_i,f_j$ 第二维做子集卷积。那么每条限制对转移是否成立也是明晰的，注意到为了去重需要给每个 $u$ 的 $S$ 强制给定一个顺序，考虑给每个 $S$ 钦定一个特殊点，转移合并到 $S$ 时强制 $u$ 的连通块包含特殊点即可。时间复杂度 $O(3^nnk)$。

CF1086F

考虑将权值拆到每个时间上，定义 $f(x)$ 为 $x$ 时刻的矩形面积并大小，那么答案就是 $tf(t)-\sum_{i<t}f(i)$。一个做法是考虑将 $f(x) $分为 $O(n^2)$ 段，每一段是由两个矩形的相交时刻来决定的，每一段内部都是一个二次函数，因此可以拉格朗日插值出来答案。时间复杂度 $O(n^3\log n)$。注意到类似于春测 T4，这个面积大小可以容斥计算。具体而言，求矩形交，然后容斥。枚举一个子集 $S\subseteq\lbrace1,2,\cdots,n\rbrace$，计算出 $0\sim t-1$ 时刻的矩形交的面积之和，乘上容斥系数 $(-1)^{|S|-1}$ 计入最终答案。容易发现对于某个时刻的矩形面积交就是 $\max(0,(2t+1-d_x))\max(0,(2t+1-d_y))$。其中 $d_x,d_y$ 是两维的极差。注意到这个东西求和是可以 $O(1)$ 计算的，因为极差是确定的，中间的乘积是可以分段解决的。那么考虑 $d_x,d_y$ 分别只与最靠左以及最靠右。那么考虑固定 $x$ 维的左端点扫描右端点，我们关心 $y$ 轴的极值。值得注意的是，如果一个点四周都有点，那么这个点不会对 $f(S)$ 造成影响，也就是 $f(S)=f(S\cup\lbrace i\rbrace)$，但是这两种情况的容斥系数一个是 $1$ 一个是 $-1$，可以直接抵消掉。因而，对于 $x$ 左右边界点，在 $y$ 轴中间的矩形 $((x_l,y_l),(x_r,y_r))$ 不能有点，那么两边往上下最多拓展一次，只会产生至多 $4$ 个矩形。直接把这些都找出来就好了，时间复杂度 $O(n^2)$。

P11149

考虑直接 dp，$f_{u,i}$ 表示以 $u$ 为根的连通块个数，使得该连通块的颜色仅为 $a_u$ 与 $i$，$i=0$ 表示这是一个单色块。容易用线段树合并来做，因为大部分转移都是整体合并与乘，外加 $O(n)$ 次单点修改，时间复杂度 $O(n\log n)$。

P9351

考虑一条路径所需要的最小花费，对于 $k=1$ 的部分分显然就是朴素的 $\text{01BFS}$，对于一个障碍点走过去需要花费 $1$ 的代价，走到空点的代价是 $0$。考虑拓展，进入一个障碍点时需要考虑清除其障碍，那么事实上我们只需要考虑这些清除障碍的点作为事实上产生代价的点就行了。对于一个点，可以走到以其为中心，边长为 $2k+1$ 的正方形中除了四个角上的任意一个点。那么就是一个点对一个大区域连代价为 $1$ 的边，肯定要考虑优化建图。考虑怎么刻画这个正方形：往四联通方向以 $1$ 的代价走一步，然后再免费走最多 $k-1$ 步的八连通。因此对一个点的描述应该为，剩余 $y$ 步走八连通的机会，$f_{x,y}$ 表示到达 $x$ 剩余 $y$ 步八连通的最小代价。使用 $\text{01BFS}$，按照 dis 为第一关键字，剩余步数为第二关键字，bfs 过程中一个点访问多次一定不优，时间复杂度 $O(RC)$。

QOJ5363

nfls 这都搬的啥玩意。考虑直接 dp，$f_{i,j}$ 表示走了 $i$ 轮最后停在了点 $j$ 的最小代价。那么转移就是跑 $m$ 轮，难点在于求出 $w(l,r)$ 表示 $l,r$ 分成一段的代价。我们知道一个 $w$ 需要将所有关键点按照 dfs 序排序然后维护 $\sum \text{dis}(p_i,p_{(i+1)\bmod m})$。然后这个东西 $w(l,r)$ 满足四边形不等式，因此是有决策单调性的。那么可以分治来维护决策单调性，分治做法可以支持动态维护当前的 $w(l,r)$，因为让 $l,r$ 指针移动是好维护的，类似莫队加入删除复杂度不变。时间复杂度 $O(nm\log n)$。

20241010

becoder D4.5T2

简单模拟题。

CF1776J

思路都很自然，顺着推下来就没了。

$k$ 维超立方体我哪会啊？考虑直接求出最终两个点的最短路。对于 $G_k$ 研究一些性质。考虑用二进制的形式来描述每一个点，每次分裂形如对 $x$ 分裂成 $\overline{x0},\overline{x1}$。那么最终一个点衍生出的点下标就可以用一个 $k$ 位二进制数来描述，并且 $2^k$ 种每种都会取到。不难发现，对于同一个点 $u$ 衍生出的 $u_x,u_y$ 而言，$u_x,u_y$ 有边当且仅当 $\text{popcount}(x\text{ xor }y)=1$。先考虑 $c_u=c_v$ 的，那么 $u_x,u_y$ 有边当且仅当 $x=y$。相应的，$c_u\ne c_v$ 时，$x,y$ 有边当且仅当 $x=\text{flip}(y)$，其中 $\text{flip}(t)$ 表示对 $t$ 的每一位都取反。那么考虑 $u_x\to v_y$ 的最短路。显然一条路径要么在中间走额外边要么在走内部边。注意到走内部边的过程在哪里都是一样的，考虑一条路径走了奇数还是偶数条 $c_u\ne c_v$ 的边，因为这类边每次都相当于 $\text{flip}$ 了当前的 $x$，那么考虑中间走的路径有：

偶数条 $c_u\ne c_v$，那么离开内部边时下标为 $t$，最终走到的也是 $t$。我们直接令 $t=y$ 就行了，答案分为 $x\to t$ 的内部边以及偶数条 $u_t\to v_t$ 的最短路。
同理可以找出奇数条 $u_{\text{flip}(y)}\to v_y$ 的最短路。

实现上，可以将一个点拆为两个点。时间复杂度 $O(n^3)$。

20241010 square

给定一个 $01$ 矩阵，求最大的正方形使得边上都是 $1$。

首先考虑预处理出 $l_{i,j},r_{i,j},u_{i,j},d_{i,j}$ 分别表示四个方向的 $1$ 的连续段的长度。我们发现判定一个答案 $c$ 是否存在的可行性甚至比直接固定一个顶点去找还容易。我们发现只需要判定 $(x+c,y+c)$ 的 $l,u$ 与 $(x,y)$ 的 $r,d$，这样只有两个点，直接枚举是 $O(n^3)$ 的。独立枚举太消耗时间了！我们希望对于一个顶点，去处理更多的关于左顶点的信息。注意到独立枚举时判定的左上角连起来就构成了一条对角线，那么我们考虑直接枚举所有 $n+m$ 条对角线，要求正方形的两个顶点都在这条对角线，那么一个右下顶点的 $k_1=\min(l,u)$，一个左上顶点的 $k_2=\min(r,d)$。我们希望在最近 $k_1$ 去找，那么直接维护一个单调栈表示当前有用的点就好了。时间复杂度 $O(n^2)$。

20241010 walk

考虑一个数轴 $[1,m]$，初始小 Z 在位置 $1$ ，一共进行 $n$ 次行动，每次可以向左或右移动一个单位或者在原地不动，问一共有多少种行动方案使得最后小 Z 仍在位置 $1$。$n\leq 3\times 10^5$。

显然 $m>n$ 是没有用的，可以直接对 $n$ 取 $\min$。我们希望计数 $f(x)$ 表示走了 $x$ 步向左或者向右的，然后对于 $f(x)$ 插入 $n-x$ 个不动的操作求和后求出最终答案。考虑直接求出所有的 $f(x)$。我们知道对于这个问题，解决的复杂度是 $O(\frac{n+m}{|y_1-y_2|})$：考虑网格图只能往上或往右，求出 $(1,1)\to (n,m)$ 不触碰直线 $y=x+y_1,y=x+y_2$ 的方案数。那么 $y_1,y_2$ 都是确定的，即 $y_2=m+1,y_1=-1$，我们要对 $n$ 组不同的 $(n,m)$ 求解。每次的复杂度大概就是 $O(\frac{n}{m})$，整体复杂度是 $O(\frac{n^2}{m})$，$m$ 很小时不可接受。但是我们其实有显然的 $O(nm)$ 做法：$f_{i,j}$ 表示 $i$ 时刻在 $j$ 的方案数。将两个 $O(nm)$ 以及 $O(\frac{n^2}{m})$ 的放在一起就好了，也就是对于 $m\leq \sqrt n$ 跑朴素 dp，否则跑反射容斥。时间复杂度 $O(n\sqrt n)$。

反射容斥：不触碰两条直线的网格图路径计数做法

CF1776M

注意到 $n$ 为偶数时，答案一定为 $n$，因为最后可以只剩下 $n$ 以及周围的两个点，因为 $n$ 是偶数，此时 B 会去取一个周围的点，此时 A 就一定可以取到 $n$。下面只讨论 $n$ 为奇数的情况。注意到答案可以直接二分，判定最终答案能否 $\ge mid$ 时直接将标号 $\ge mid$ 的视为 $1$，否则视为 $0$。问题就是判定 A 是否可以取到一个 $1$。显然原树如果有叶子的值是 $1$ 那么显然是可以的。否则考虑一个终局状态，使得 AB 玩到只剩这样一个状态，让这个状态都可以贡献到答案。我们考虑找一些使得 A 能必胜的状态。我们肯定希望 A 去剪叶子。那么考虑某些 $1$ 点构成的点集 $S$ 使得 A 无论如何都可以取到 $S_i$。注意到一个距离为奇数的点对 $x,y$，可以保证取到 $x,y$ 中的至少一个，大概就是 $x,y$ 其中一个露在外面的时候一定是 A 来操作。三个两两距离为偶数的点也可以保证至少取到一个。可以直接 dp 维护这两个过程，时间复杂度 $O(n\log n)$。

CF1456E

考虑从高到低进行数位 dp。先刻画怎么进行 $l\leq x\leq r$ 的限制：就是直接设计 $2\times 2=4$ 种状态，分别是是否顶着 $l$ 的前缀，是否顶着 $r$ 的前缀。考虑每个数在 $[0,h_i]$ 的位可以自由选，也就是两个脱离 $l,r$ 前缀的位置的 $\min$ 在 $h_i$。那么一个数就一定是和 $l,r$ 其中一个的 $\text{lcp}$，后面可以任意填。那么如果确定一个数是和 $\text{lcp}$ 相同的，可以用 $0/1$ 来描述是与 $l$ 相同还是与 $r$ 相同，另一个就是最底下的位是否已经被翻转，会影响。脱离限制之后，一定是两边都全放 $0$ 或者全放 $1$。那么考虑这一位中间如果都是脱离限制的，这一位是否会产生贡献就取决于连接的两个数在这一位是否相同。如果刻画第 $c$ 位造成的贡献，我们可以找出来所有 $h_i\geq c$ 的连续段，形成了若干段子区间，那么这些子区间的贡献就取决于两端连接的数的状态，而这两个数都是顶着界的。因此想区间 dp，那么维护一个 $f_{c,l,r,0/1,0/1,0/1,0/1}$ 表示考虑最高的 $h$ 位，在原序列维护 $[l,r]$ 的答案，此时 $l-1,r+1$ 的上下界限制分别用两个 $0/1$ 来描述。其中我们要求 $h_{l-1},h_{r+1}<c$。转移直接枚举断点 $k$ 表示 $k$ 在第 $c$ 位之后自由选取，由 $f_{l,k-1},f_{k+1,r}$ 拼合，或者直接继承无断点即可。使用记忆化搜索，时间复杂度 $O(n^3k)$。

P6662

谁出的三合一？

Subtask 1，$n\leq 15$。

Subtask 2，$m\leq 24$。

Subtask 3，图由若干个环构成。

20241007 联考 T3

每次操作大概就是剪掉一个连通块。难点在于想到用决策树来刻画一个策略，让它变成确定性的。考虑对于这个确定形态的决策树，令其除了叶子节点都有两个子节点。那么其询问的轮数就是在决策树上的深度，每次往决策树左右的一个子树中走。定义一个点（原树上的边）的标号 $k_{u,v}$ 是 $m+1-dep$。那么问题在于确定这个决策树。先考虑对于一个决策树 $G=(V,E)$ 的答案，停在 $u$ 就要求其邻边均被选入 $E$，其期望得分 / 权值即为 $w_up_{m+1-\min(k_{u,v})}$。事实上一个决策树形态可以由每个边的 $k$ 唯一确定，我们要求 $\forall k_{e_1}=k_{e_2},\exist e_3\in\text{path}(e_1,e_2),k_{e_3}>k_{e_1}$。为了方便进行树上 dp，考虑将原树定根为 $1$，并且让树是外向的。类似于点分治的思想，考虑用到叶子路径的 $k$ 的前缀 $\max$ 集合 $S(x)$ 来刻画路径。$x$ 可以是边或点。那么一个标号方案要求 $u$ 的两条出边 $e_1,e_2$ 有 $S(e_1)\cap S(e_2)\subseteq\lbrace0\rbrace$，并且 $k_{(u,v)}\notin S(v)$。直接树上 dp，$f_{u,s}$ 表示 $S((u,fa_u))=s$ 的最大期望即可。时间复杂度 $O(n3^k+nk2^k)$。

20241011

P11151

这种锤子最优化东西还是要想贪心啊。

运用贪心的策略，考虑对于一次询问，需要决策一个位置是否加油，线性扫考虑当前在 $i$，那么贪心考虑下一个油价最小的位置 $nxt_i$，在 $nxt_i>t$ 时应该考虑 $t$，应该加到 $\min(\sum_{t=i}^{j-1}l_t,V)$。对应的含义是，如果 $nxt_i$ 可以在 $i$ 内到达，那么我们就加到只有能到达 $nxt_i$ 即可，否则在 $nxt_i$ 的位置加一定不劣。首先我们考虑 $[i,nxt_i]$ 一定是一个【仅包含或相离】的结构。可以加速跳加油的点，如果 $nxt_i$ 是无法抵达的，容易发现对于 $i$ 下一个需要加油的点是确定的，只是产生的费用不同。不难发现就是 $i$ 往后 $V$ 的距离中 $p_j$ 最小的 $j$。那么所有的 $nxt$ 都是确定的，可以考虑建立树上结构 $i\to nxt_i$，此时建立一个虚点 $n+1$ 作为树根就行了。注意到，就可能没跳到 $t$ 的时候就可以直接一口气冲过去了，需要倍增找到哪个点就可以直接冲到 $t$，维护一下 $anc_{i,j}$ 表示 $i$ 的 $2^j$ 级祖先的节点标号就好了。那么考虑怎么解决初始油量的问题，也就是定位到树上哪个节点。我们可以接着贪心，我们发现在 $\text{dis}(i,nxt_i)\leq V$ 加油的优先级是更高的，那么可以对此也倍增加速这一段跳好点的过程。时间复杂度 $O((n+m)\log n)$。实现上跳到倒数第二步就行了，暴力执行最后一个跳到 $t$ 的操作。

P8189

显然原问题就是每次询问两个集合的答案，输出两个相乘。考虑将选择的点视为 $p_i$，那么就是给定一张图，求将整个图划分为一堆简单环，也就是给每个 $i$ 选择出边 $p_i$，计算合法的方案数。考虑 $h_S$ 表示 $S$ 构成的环方案数，那么每次钦定 $\text{lowbit}$ 被更新防止重复，做一遍子集 $\exp$ 就出答案了。对于一个环，链头可以直接钦定一个。只要考虑链然后统计时假设链尾和链头有边就行了，$f_{S,i}$ 表示对于集合 $S$ 构成的环，链尾是 $i$ 的方案数。这样做的复杂度是 $O(3^n+n^22^n)$。扫了眼题解，啥玩意，那个子集合并是不必要的，给所有集合钦定个顺序直接进行 $f$ 的转移就可以做到 $O(2^nn^2)$。

LOJ2395

为什么我第一眼是二分然后才想到倍增啊？发现判定一个步数是否可达是容易的，改成倍增就可以消掉一个 $\log$。

考虑优化原图边数，我们可以不太管这个所谓的换乘。考虑求出 $lst,nxt$ 分别表示前驱和后继，为 $\ge a_i$ 的点，容易单调栈 $O(n)$ 求得。虽然边数是对的，但是我们显然不能直接跑最短路，考虑拓展，发现这个东西是类似于倍增的东西，每次跳。然后这个结构是【仅相离或包含】的，考虑直接对于这种结构建树，父节点为极短的包含它的区间。直接对于两个 $[s,s],[t,t]$ 的区间求一下 lca 即可。不需要显性建树，直接处理下倍增就行。时间复杂度 $O((n+q)\log n)$。不用建树理解也是行的，根据那个结构的分析，一定是单调地往右一直跳之后往回跳。

P11110

先考虑 $b=0$ 怎么做，将物品按照重量排序之后，如果一个前缀可以凑出 $\leq k$ 的所有数，那么加入一个 $1\leq c\leq k+1$ 的物品就可以凑出 $\leq c+k$ 的所有数，不然连 $k+1$ 都无法凑出。拓展这个，考虑一个必要条件：要求所有 $0\leq x\leq a,0\leq y\leq b$，所有物品重量 $\leq \min(k,\max(x,y))$ 的重量之和 $\ge x+y$，这个是充分的。由 $b=0$ 那个做法可以得知哦。不妨设 $a\leq b$，那么考虑先对于 $x,y\leq a$ 的做判断，只需要考虑 $x=y$ 的情况。那么相当于这个分界线在移动，只需要关心所有 $x=y=w_i-1$（这样显然是最极端的）以及 $x=y=a$ 的情况。类似的，可以设 $x=a$，$y$ 也只需要考虑所有 $w_i-1$ 以及 $b$。需要关心的信息总量是 $O(n)$ 的，可以前缀最大值预处理。

20241012

CF1746F

哈希。考虑对每种颜色随机赋权，那么一个好区间的必要条件是权值和为 $k$ 的倍数。错判的概率是 $1/k$，跑 $20$ 遍就好了。使用树状数组维护区间权值和即可。

P7688

关键性质：一个 $2$ 价区间替换为两个 $1$ 价区间不优。也就是假设我们可以最多选出 $mx$ 个不相交的区间 $[x_i,x_i+k-1]$，存在一组最优解选出了 $mx$ 个 $2$ 价区间。现在问题就是要最大化 $1$ 价区间的数量。找出所有区间做 dp，$f_i$ 表示 $i$ 作为某个 $2$ 价区间的结尾，包含它在这个前缀最多选出来多少 $2$ 价区间。$g_i$ 表示最大化 $f_i$ 的前提下，这个前缀能选出来的 $1$ 价区间数量最大值。$f$ 可以 $O(n)$ 直接扫出来，问题在于 $g$。对大样例打表之后，注意到 $f$ 的结构是一堆连续段，而对于同一个 $f$ 的 $g$，一段前缀是 $x$，后面就是 $x+1$。所以对于每种 $f$ 有用的转移点最多两个，也就是第一个 $x$ 和第一个 $x+1$。也就可以做到 $O(1)$ 转移了。时间复杂度 $O(n+m)$，输出方案有点烦。

CF1712F

卡我单 $\log$，模拟赛搬题人素质呢。

考虑直接 BFS 处理出所有关键点到每个点的最短距离 $a_i$。那么就是要求出 $\max(\min(\text{dis}(u,v),a_u+a_v+k)$。考虑枚举 $u,v$ 的 $\text{lca}$，那么此时 $u,v$ 就只和到 $\text{lca}$ 的距离 $i,j$ 有关。而我们希望对于同一个 $i$ 最大化 $a_u$，同一个 $j$ 最大化 $a_v$，不难想到长链剖分维护 $f_{u,i}$ 为到 $u$ 距离为 $i$ 的最大的 $a_v$。每次直接继承长儿子，对于短儿子对应的短链的贡献，直接暴力枚举短链合并即可。$f$ 做前缀 $\max$ 处理之后可以直接二分处理出两个函数的交点。时间复杂度 $O(qn\log n)$。

CF1726G

场上假做法过了（事实上是没判无解）。考虑 $b_i=1$ 的做法，如果最后都变成了值 $x$，那么一定满足 $x\ge \max(a_i)$，并且我们考虑初始值 $<x$ 的数，如果同一数值存在多个就寄了。因为这两个数的 $\Delta$ 必定不相同。容易发现，当且仅当 $x=\min(a_i)+n-1$ 时才有可能有解。不难发现这个也可以拓展到全部情况哦，并且最小值唯一且必须 $b$ 为 $1$。对于 $b_i=1$ 的部分分就是考虑只能最大值作为等价类互相换，乘一个下降幂表示可以任意插入，剩下的数顺序唯一。拓展的话，我们发现对于 $a$ 相同的，至多只能有一个 $b$ 为 $1$。那么考虑从小到大插入数值，不难发现 $b$ 为 $0$ 且 $a$ 数值相同的内部是一个等价类，可以乘以一个阶乘，并且 $b=0$ 内部一定是 $a$ 不减顺序操作。$b=1$ 考虑两者 $\Delta$ 的大小关系，发现 $b=1$ 内部一定按照递减顺序操作。考虑两者合起来怎么做，对于每种等价类而言：

$a=t,b=0$ 的需要 $t-\min(a_i)$ 个 $\leq i$ 的数被放在之后操作。
$a=t,b=1$ 的需要 $\min(a_i)+n-1-t$ 个 $<i$ 的数被放在后面操作。

将值域正序枚举，实时判断存在足量的数，那么这些数实际就会放在偏后的位置来操作就可以判断是否合法。

时间复杂度 $O(n)$。

P7830

神秘操作要考虑极端情况，比如在本题可以每个点都指向父亲。根节点随意。此时就会按照欧拉序对着整棵树完整走一遍，此时就形成了一个周期哦。

不妨设树根是 $1$。注意到一个点指向父亲之后，再进入走出这一轮之后就会维持这个指向父亲的状态。问题是在走到这个周期前的若干步怎么处理。注意到一个点经过最多两次后就可以被指向父亲，定义一个点是好的当且仅当这个点是根或者这个点已经指向父亲。那么考虑从根开始维护这个好点的连通块，只需要考虑若干关键步骤，也就是连通块拓展的时刻。对于询问按照 $k$ 离线排序，时间复杂度 $O(n\log n)$。有点太难写了。具体的实现上，只需要关注到每一轮拓展的只会是下一轮拓展的基础即可，模拟加点过程即可。

UOJ724

纸老虎。把我唬住了。

等价于比较 $s[\min(x,y):\max(x,y)-1]$ 以及 $s[\min(x,y)+1:\max(x,y)]$ 的字典序。先考虑 $x<y$ 的情况，那么按照字典序的定义就是比较 $[x,y)$ 区间中第一个 $s_i\ne s_{i+1}$ 的位置，不存在也就是两个区间完全相等也即 $[x,y]$ 都是同种字符是显然符合要求的。存在不同时，如果 $x\leq y$ 就要求 $s_i<s_{i+1}$，不然就要求 $s_{i}>s_{i+1}$。那么问题就转化为给定若干组 $(x,y)$，每组都必须满足二者其一：

$[x,y]$ 均为同一种字符。
$[x,y)$ 首个 $s_i\neq s_{i+1}$ 需要满足给定的偏序关系。

这样看上去是比较很多东西，事实上只需要考虑相邻点对的偏序关系即可。

显然这样子我们可以刻画成连续段状物。$n$ 很大，直接来个前缀的朴素状态就好了啊。注意到字符串计数题很大可能是与 $\Sigma$ 有关的，考虑直接把这个扔进状态。那么考虑 $f_{i,j}$ 表示前 $i$ 个字符中，$s_i=j$ 的合法方案数。转移考虑怎么接上 $s_{i-1}$，如果 $s_{i-1}=s_i$ 就可以直接继承，否则需要分讨大小关系。枚举 $i-1$ 的连续段从哪里开始啊，假设上一个是 $s_k\ne s_{k+1}$。考虑原来的限制，有两种：

$x<y$ 有 $[x,y)$ 的小于号限制。
$x>y$ 有 $[x,y)$ 的大于号限制。

转移时，我们需要考虑需要迎合哪些需要确定的限制。已经满足的不用管，管不到的也不用管。

对于 $s_{i-1}<s_i$，那么枚举连续段起点的话就要求不存在 $l\ge k,i<r$ 的大于号限制。那么合法的 $k$ 是一段后缀，此时转移的贡献就形如 $f_{k+1,j}-f_{k,j}$，对这个东西后缀和以下，然后合法的 $k$ 是一段后缀，std::set 维护。对于 $s_{i-1}>s_i$ 同理。

时间复杂度 $O(n\log n+n\Sigma)$。

ARC163D

竞赛图缩 SCC 之后一定是链，并且链上每个点都会向后连边。结论是，考虑给这个链断成两部分计数，也就是计数：划分成两个点集 $S,T$，要求 $|T|>0$，并且 $\forall u\in S,v\in T$，方向均为 $u\to v$ 的方案数。显然 $S,T$ 与链的前后缀形成双射。只需要对这个点集划分方案计数即可。直接对此 dp，维护 $f_{i,j,k}$ 表示划分了 $i$ 个点，$|S|=j$，正向边有 $k$ 条的方案数，转移考虑 $i$ 放到 $S$ 还是 $T$ 即可。时间复杂度 $O(n^5)$。

标签：2024.10,log,记录,sum,leq,考虑,复杂度,dp
From： https://www.cnblogs.com/nullptr-qwq/p/18466324

2024.10 记录（1）

\(2024\) 年 \(10\) 月记录