2024.5 口胡记录

随便做做（

Luogu P10395（未实现）

难度：[7] 标签：dp、ds、树状数组

首先 $a$ 里面相同的元素必须分布在连续一段内。

然后对所有 $x$，设 $x$ 是序列 $a$ 中第 $r_x$ 个出现的，对所有 $i$ 将 $b_i$ 替换为 $r_{b_i}$，再在两侧分别补一个 $0$ 和 $k+1$。问题转化为在 $b$ 中找一个子序列 $0=c_1<c_2<\cdots<c_s=m+1$，使得：

• $b_{c_i}\leq b_{c_{i+1}}$；
• $b_{c_{i+1}}-b_{c_i}\leq c_{i+1}-c_i$；
• $s$ 尽量大。

按二元组（$b$ 的值，下标）递增考虑每一个位置，将 $i$ 位置的 dp 值记在树状数组的 $i-b_i$ 位置上，每次转移在 $i-b_i$ 的前缀中查询最大值。复杂度 $O(m\log n)$。

Luogu P10399（未实现）

难度：[9+] 标签：ds、线段树、暴力

首先对于任意一次操作，我们肯定是贪心地选择使得结果更大的那个。然后由于 $b\geq 2$，所以经过 $\log V$ 次之后就是无脑选乘法。

我们考虑直接线段树维护这个结构，问题变为已知两段相邻区间 $[l,m],(m,r]$ 的答案，要合并出整个区间 $[l,r]$ 的答案。

为了做这个合并，我们考虑每一个左端点在分界点左侧的区间，右端点在分界点右侧的区间 $[l',r']$。固定一个 $m<r'\leq r$，那么对于每一个 $l\leq l'\leq m-\log_2 V$，区间 $[l',r']$ 的答案都是区间 $[l',m]$ 的答案乘上 $\prod_{i=m+1}^{r'} b_i$。

于是取定 $K=\log_2V$，那么对于所有 $l\leq l'\leq m-K,m<r'\leq r$ 的区间 $[l',r']$，其贡献就是所有 $l\leq l'\leq m-K$ 的区间 $[l',m]$ 的答案之和乘上 $\sum_{i=m+1}^{r}\prod_{j=m+1}^{i}b_j$。后者再维护一个 $b$ 的区间积即可维护。

先不管前者的维护，考虑 $m-K<l'\leq l,m<r'\leq r$ 的区间 $[l',r']$ 的贡献。这里我们可以暴力，考虑算出区间 $[l',l'],[l',l'+1],\cdots,[l',l'+K]$ 的答案之和，然后乘上 $\sum_{i=l'+K+1}^{r}\prod_{j=l'+K+1}^{i}b_j$。前者我们可以单独维护一个数组，维护左端点固定，区间长度 $\leq K$ 时，答案关于区间右端点的前缀和。在修改的时候可以暴力重新计算所有受到影响的位置。维护这个数组的复杂度为 $O(n\log V+q\log^2V)$，查询答案和单次 $O(1)$。后者我们记录 $b$ 的乘法逆元，即可在递增枚举 $l'$ 时，从 $m+1$ 向右递推。

于是如果我们可以维护所有 $l\leq l'\leq m-K$ 的区间 $[l',m]$ 的答案之和，我们就可以 $O(\log V)$ 合并两个区间的答案。而维护前面那个东西除了最后乘的系数变成 $b$ 的后缀积以外，和维护答案都是一样的。

从而把这个东西放到线段树上，即可做到 $O(n\log V+q\log^2V+q\log n\log V)$ 的总复杂度。

Luogu P10408（未实现）

难度：[8] 标签：ds、分块、折半

将位的集合折半，对其中一半做高维前缀和，总共做 $2^{n/2}$ 个大小均为 $2^{n/2}$ 的高维前缀和。

这样单点更新的时候，只影响到一个高维前缀和，即 $2^{n/2}$ 个数；查询子集和的时候，只需要枚举 $2^{n/2}$ 个高维前缀和，每个前缀和内查一个点。复杂度 $O(2^{n/2}q)$。