RDOI Round #1 solution

猫树

由于必须走到点 $n+1$，所以先减掉贡献，然后二分到一个宽松的下界，使得能获得 $\ge mid$ 的金币的操作都能进行。

剩下的操作显然不足 $n$ 次，用堆模拟即可。

---

记忆余晖

$\Theta(3^n)$ 的做法是原题，故不做阐述。

正解为 $\Theta(2^nn^2)$ 的做法，如下：

考虑把 $1\sim n$ 依次插入，设 $g_i$ 表示前缀 $1\sim i$ 的 $LIS$ 长度。

由定义可知 $0\leq g_{i+1} - g_{i}\leq 1$ 于 $n\leq 21$，状压差分储存。

设现在插入 $i$，插在位置 $j$：

$g_j$ 会是 $g_{j+1}+1$，然后会更新一段从 $j$ 开始的前缀为 $g_j$。

可以借助一下代码理解：

int tps( 1<<(j-1) );
int lows( s&(tps-1) ),highs( s^lows );
int mark( lows^tps^(highs<<1)^(lowbit(highs<<1)) );

---

乘积、欧拉函数、求和

首先，我们知道，$φ(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_k})$，其中 $p_1 \sim p_k$ 是 $n$ 的互不相同的质因数。

知道这个之后，我们就可以先线性筛 + 质因数分解，以 $\Theta(m \frac{\sqrt m}{\ln {\sqrt m}})$ 的复杂度预处理出 $1 \sim m$ 中所有数的质因数集合，设 $i$ 的质因数集合为 $P_i$。

那么，我们考虑 $φ(uv)$，可以发现，$φ(uv)=uv(1-\frac{1}{q_1})(1-\frac{1}{q_2})\dots(1-\frac{1}{q_k})$，其中 $q_1 \sim q_k$ 是 $u$ 与 $v$ 的质因数集合的并集中的元素，因为 $u$ 与 $v$ 中相同的质因数只能做一次贡献。

为了方便，我们重新定义 $\gcd$ 函数。

令 $\gcd(i,j) =\prod(P_i \cap P_j)$。

通过上述预处理和 set​ 维护就可以写出 $\Theta(\min(n,m)^2)$ 的暴力，预期得分 $30pts$。

考虑特殊性质 $A$，即只有加入 $x_i$ 的操作的做法。这种题目一般来说都要增量式计算贡献，即对于 $x_i$ 考虑之前 $S$ 中所有的数与它的贡献。可以发现，$\leq 5 \times 10^5$ 的数中，每个数不同质因数的个数不会超过 $6$，因为 $2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 =510510 > 5 \times 10^5$，这也告诉我们，确定 $x_i$ 后，它与其它数的 $\gcd$ 最多只有 $2^6$ 种。设数组 $V_i$ 初值为 $0$，每加入一个数便在其所有可能的 $\gcd$ 对应的 $V$ 上加上它本身。这样就可以对于一个加入的 $x_i$，枚举可能的 $\gcd$ 来计算答案。然而，这样显然会算重，例如 $\gcd$ 为 $6$ 的会在 $\gcd$ 为 $6,3,2,1$ 时被算到。但是，可以发现算重的一定是真正 $\gcd$ 的子集。所以复制一个 $V$ 数组为 $A$，从大到小枚举可能的 $\gcd$，若当前枚举到的 $\gcd$ 为 $d$，则 $A$ 中 $d$ 的因数位置的值全部减去 $A_d$ 即可。可以发现这是在做一个容斥。这样的话，预期得分就有 $60pts$ 了。

删除操作和加入操作的做法几乎一致，故不再赘述。预期得分 $100pts$。

但是，这样做法的时间复杂度是 $\Theta(n \times (2^{\max(siz_{P_i})}+3^{\max(siz_{P_i})}))$ 的 ，并且常数较大，所以容易被卡常。于是就有了数据随机生成和特殊性质 $A$。特殊性质 $A$ 因为不能在一个数上反复横跳所以显然达不到该复杂度上界。而数据随机生成的期望修改与查询次数都较低，约为 $50$。

---

重逢之时

此题每次询问区间，又未要求在线，可用扫描线的思路，枚举一个端点，数据结构维护另一个端点的值。

分析可得，从 $i-1$ 到 $i$ 的增量是不好处理的，所以不能每次利用相邻数的信息来更新。

考虑 $i$ 本身，对前面的数按与 $a_i$ 的大小关系分讨。对于 $a_j<a_i,j<i$ 此情况最大的 $j$ ，一定可以可以用 $a_i-a_j$ 更新左端点 $\in[1,j]$ 的区间。此时，对于 $abs(a_k-a_j) \leq a_i-a_k,k<j$，就不需要去更新了，因为在 $j$ 作为加入标号时，对于左端点 $\in[1,k]$ 的区间已经更新过 $abs(a_k-a_j)$，所以发现合法的 $k$ 满足 $a_k>\frac{a_i+a_j}{2}$。发现每次值域减半，所以理论更新次数为 $\log V$ 级别。

考虑如何实现，维护端点答案需要一颗线段树，同时需要知道形如 $a_i<a_j,i<j$ 的最大的 $j$ ，可以对权值开线段树，$i$ 表示权值为 $i$ 的最大编号，查询可以二分。发现对于对于原序列的修改是前缀 $\min$ ，区间求和，直接维护是不好做的，但由于是前缀 $\min$ ，那么答案序列一定是有单调性的，所以就可以先二分出可以更新的区间，然后再用区间推平（赋值）做修改，这样就能够求和了。

总时间复杂度 $\Theta(n\log^2V+q\log n)$。

‍