Untitled
6.15 题解
A - 星际蛋糕推销
Des
你有 $n$ 个数，我们希望这 $n$ 个数都是奇数。因此，我们每一次会对于最左边的一个偶数进行减半操作，即把 $a_i$ 变成两个 $\frac{a_i}{2}$ 并放在原位置上。完成操作后求有 $m$ 个询问求第 $i$ 个位置是什么。
Sol
显然，若将 $a_i$ 质因数分解，则有：
$$a_i = \prod_{p\in \mathcal{P}} p_i^{\alpha_i}$$
其中 $p_1=2$，因此它会被切 $2^{\alpha_1}$ 次。这样，我们就能够知道每一个数会被分成多少个数，维护一个前缀和表示每个数产生的数截止到哪里，然后每一次二分查找答案即可。复杂度 $O(n\log n)$。
B - 狡猾的商人
Des
给定 $m$ 次询问并告诉你答案。具体的，每一次询问形如 $l,r,s$，表示 $\sum\limits_{i=l}^ra_i=s$。你需要判断存不存在数列 $a_i$ 满足条件。
Sol
让我们把询问写成前缀和的形式。具体的，对于询问 $l,r,s$，我们有 $s_r-s_{l-1} = s$。也就是说，从 $l-1\to r$ 经过了 $s$ 才能到达。这个东西我们考虑建图，那么它们合法当且仅当图上的环都自洽。也就是说，如果有 $u\to x$ 权值为 $a$，$x\to v$ 权值为 $b$，则一定有 $u\to v$ 权值为 $a+b$。
具体的，对于询问 $l,r,s$，我们建立边 $(l-1, r, s)$ 和 $(r, l-1, -s)$，然后跑一遍 $\text{Floyd}$ 传递闭包，如果某一条边不存在就更新，否则就判断是否有 ma[i][j] = ma[i][k] + ma[k][j]。
（听说这个题还有 $O(n·\alpha(n))$ 的并查集做法，但是 $100$ 的 $n$ 为什么不跑一个简单优美的 $\text{Floyd}$ 呢/doge）
C - 字串距离
Des
对于两个字符串 $s_1$，$s_2$，我们可以在任意地方补足任意的空格，使得最终的两个字符串长度相等。这样，我们有代价的公式：
$$\sum_{i=1}^{len} |s1_i-s2_i|$$
其中若 $s1_i$ 或 $s2_i$ 为空格，则规定 $|s1_i-s2_i|=k$，而若 $s1_i$ 和 $s2_i$ 都为空格，则有 $|s1_i-s2_i| = 0$。
Sol
不难想到，我们设 $f_{i,j}$ 表示 $s1$ 进行到 $i$，$s2$ 进行到 $j$ 的最小代价。其中 $f_{i,j}$ 可以由 $f_{i-1,j}$、$f_{i,j-1}$、$f_{i-1,j-1}$ 三个状态转移过来。其中前两个表示分别用空格去匹配别的字符，而第三个表示用 $s1_{i-1}$ 去匹配 $s2_{j-1}$，因此，就有如下转移方程：
$$f_{i,j} = \min{f_{i-1,j}+k, f_{i,j-1}+k,f_{i-1,j-1}+|s1_{i-1}-s2_{j-1}|}$$
复杂度 $O(n^2)$。
D - Marvolo Gaunt’s Ring
Des
给定序列 $a_n$ 和常数 $p,q,r$，求三元组 $(i,j,k)$ 满足 $i\le j\le k$ 且最小化 $pa_i+qa_j+ra_k$。
Sol
维护一个前缀最大、前缀最小、后缀最大、后缀最小。然后枚举中间点 $j$，向前向后分别 $O(1)$ 求出 $pa_i+ra_k$ 的最大值即可。
注意要根据 $p,r$ 的正负情况分类讨论。
E - Running S
Des
小可喜欢跑步。
他每天早上疲惫值为 $0$，在第 $i$ 分钟可以跑 $d_i$ 米，会增加 $1$ 的疲惫值。他疲惫值最多为 $m$。同时，他也可以选择休息。但是选择休息就必须休息到 $0$ 疲惫值，其中疲惫值每分钟降低 $1$。同时，在疲惫值为 $0$ 时，他也可以选择啥也不干，并且最终的疲惫值必须为 $0$。问他最多能跑多远。
Sol
考虑动态规划。
首先我们想到的是 $f_{i,j}$ 表示前 $i$ 分钟疲惫值为 $j$ 时最远能跑多少。那么显然有转移方程：
$$f_{i,j} = f_{i-1,j-1} + d_i, j\not = 0$$
$$f_{i,0} = \min\limits_{j=i}^{\max(i-m,0)} f_{j,i-j}$$
方程 $1$ 很好弄，$O(1)$ 直接搞定，但是第二个可能需要复杂度退化一个 $m$，这不能接受。
我们考虑一种一遍填表一边刷表的方式。也就是当我们转移完 $f_{i,j}(j\not = 0)$ 时，我们令 $f_{i+j,0}\leftarrow f_{i,j}$ 即可。这样就保证了复杂度的正确性。
F - 树上染色
Des
给定一棵树，要求在树上把 $m$ 个点染成黑色，并有价值函数
$$v(E’) = \sum_{v_1,v_2\in E’} dis(v_1,v_2) + \sum_{v_1,v_2\in E-E’} dis(v_1,v_2)$$
求一种染色方式使得最大化 $v(E’)$。
Sol
仍然考虑动态规划。
$f_{u,k}$ 表示 $u$ 子树内选择 $k$ 个 对答案的贡献。考虑这和 $f_{u,k}$ 表示 $u$ 子树内选择 $k$ 个 的价值 有什么不同。
对于答案的贡献，我们是默认在 $u$ 子树之外已经选择了 $m-k$ 个其他的黑色节点的，因此对于边 $u\to v$，若有 $v$ 子树内已经选择了 $k$ 个，那么边 $u\to v$ 经过的次数就是 $k\times(m-k)$ 次，因此对答案的贡献就是 $w\times k\times (m-k)$。同理可以计算得到白点的贡献。
而价值指的是 $u$ 子树内选择 $k$ 个，而 $v$ 子树内选择 $k’$ 个的贡献，这是不好被统计的。
由第一个设的状态，我们有转移方程：
$$f_{u,j} = \max{f_{v,k} + f_{u,j-k} + w\times k\times (m-k) + w\times (sz_v-k)\times (n-m-sz_v+k)}$$
但是这样显然会 $\text{TLE}$。这是因为我们需要 $DFS$，并且每个点枚举一个 $j$ 和一个 $k$，复杂度 $O(nk^2)$。无法接受。
我们做一个上下界优化。显然，$j$ 的上下界是 $[0,\min(m,sz_u)]$，其中 $u$ 是已经遍历到的 $u$ 子树的大小。而 $k$ 的范围是 $[\max(j-sz_u+sz_v,0),\min(sz_v,m)]$。因此，式子就变成了：
$$f_{u,j} = \max_{j=0}^{\min(m,sz_u)}\max_{k=\max(j-sz_u+sz_v,0)}^{\min(sz_v,m)}{f_{v,k} + f_{u,j-k} + w\times k\times (m-k) + w\times (sz_v-k)\times (n-m-sz_v+k)}$$
为啥复杂度是对的前几篇题解写得也已经很明确了。这里需要注意的是 $j$ 需要倒序枚举，否则答案会不正确。
G - LCA
Des
给定一棵树，有 $q$ 次询问，每次询问形如 $l,r,x$，求：
$$\sum_{i=l}^r \operatorname{dep}[\operatorname{lca}(i,x)]$$
Sol
首先，我们想到把 $l,r$ 拆成两个询问，即 ${l-1, -1}$ 和 ${r,1}$，表示答案乘上 $-1/1$ 贡献到 $i$ 中。然后使用扫描线扫描当前的到了第几个节点，并且标记好以方便我们进行查询操作。
于是，现在的问题就是如何进行修改和查询。
注意到，如果有些点在 $x$ 的子树内，那么它们的 $lca$ 一定是 $x$，也就是贡献 $\operatorname{dep}[x]$。我们记 $s_x$ 表示 $x$ 子树内被标记的点的数量，那么答案一定有 $s_x\times \operatorname{dep}[x]$。
再往上一层，我们记 $y=fa_x$ 表示 $x$ 的父亲，那么显然，对于所有在 $y$ 子树内但不在 $x$ 子树内的节点和 $x$ 的最近公共祖先显然就是 $y$，那么贡献就是 $(s_y-s_x) \times \operatorname{dep}[y]$。再往上一层，记 $z = fa_y$，则有贡献 $(s_z-s_y)\times \operatorname{dep}[z]$。全部加起来，就可以得到 $s_x\times \operatorname{dep}[x] + (s_y-s_x)\operatorname{dep}[y]+(s_z-s_y)\operatorname{dep}[z]=s_x(\operatorname{dep}[x]-\operatorname{dep}[y])+s_y(\operatorname{dep}[y]-\operatorname{dep[z]})+s_z\operatorname{dep}[z]$，其中 $\operatorname{dep}[x]-\operatorname{dep}[y]=\operatorname{dep}[y]-\operatorname{dep}[z]=\operatorname{dep}[z]=1$，于是式子就是 $s_x+s_y+s_z$。
通过上面的式子我们不难推出，询问 $x$ 的值就是 $x$ 及 $x$ 所有的父亲的 $s_x$ 之和。换句话说，是 $(1,x)$ 路径上的 $s_x$ 和。
我们再来看修改会带来什么影响。我们想知道的是每个点的子树中被标记的点的数量，那么对于一个点 $x$，当它加入了树中，他所有的祖先的 $s_x$ 都应该加一。也就是在路径 $(1,x)$ 上区间 $+1$。
在回头梳理一下解题过程：
- 将询问 $l,r,x$ 拆成 $l-1,x,-1$ 和 $r,x,1$。
- 从左到右扫描节点，先进行修改再处理询问。
- 修改操作使用树剖在 $(1,x)$ 的路径上区间 $+1$。
- 查询操作使用树剖求 $(1,x)$ 路径上的区间和。
使用树剖+线段树即可。