C. Lazy Narek

dp即可； 不过一定要好好读题才行！！ 就是读题读假了和不仔细，才导致vp赛时没有调出来。这个dp的优化(或者是自然而然的处理)：数组开1维5个位置即可，不需要对m轮全部开一个位置，否则会tle。状态转移时记得滚动，不要在原数组上面改，否则会出问题(可能跑出来同一层选了两次的结果)

D. Alter the GCD

analysis

前缀和后缀和gcd自然不用多说。逐一枚举$\{l，r\}$即使每次枚举求值是$O(1)$也会tle。所以要寻求更好的方法求解。

由于一个数的质因子最多只有$\log n$个，考虑gcd prefix是单调非升的，那么有如下性质：只有最多$\log n$个位置 $i$ 使 $ prefix[i] > prefix[i+1] $ ,其余均为 $prefix[i] = prefix[i+1]$ 对suffix gcd类似。那么实际上，绝大多数前后缀gcd是相等的。如果枚举$\{l，r\}$是对于$l$或$r$都是$O(n)$，组合起来是$O(n^2)$的的话，我们枚举单个变量的前缀/后缀值可以把这个枚举降到一个$O(\log n)$的时间复杂度基于这样的观察，我们有不同的思路求解：

solve1 分治

我们枚举l，r代表的前后缀值的话，那么中间这部分怎么加进来呢?如何防止l>r呢 (毕竟不同的值都转化成了gcd value) 我们考虑设定一个枚举范围 $ [l,r],mid = (l+r)/2 $ ,枚举所有的$l \le i \le mid$和$(mid +1) \le j \le r$ 这个时候所有跨 $mid$ 和 $mid+1$ 间隙的值都被遍历到了，只剩两个子区间内部的没有被枚举。于是我们递归地取求解 $[l,mid]$ 和 $[mid+1,r]$ ，而对于 $l = r$ 的区间我们特别枚举答案 $\{l,r\}$ (因为按照前面的规则的话 $[l,r]$ 是没有贡献对的，这样会漏，但是如果我们扩大 $[l,r]$ 的贡献对范围的话，导致重复贡献将难以处理。) 通过这样的递归，或者说是分治策略，我们按值枚举不重不漏地遍历了所有组合

那么如何通过按值枚举快速求出一个枚举范围 $[l,r]$ 所有的 $value(\{i,j\})$ 呢根据前面的分治策略，我们把三段gcd的复合转化成以mid为界的两段gcd的复合：(以数组a最终的gcd为例) \[p[i] = \gcd(a_l,a_{l+1},...,a_{i-1},b_i,b_{i+1},...,b_{mid})\] \[s[j] = \gcd(b_{mid+1},b_{mid+2},...b_{j},a_{j+1},...,a_{r})\] 由于对 $a,b$ 均要求出 $p[i] , s[j]$ , 我们用map<pair<int,int>>$pmp,smp$( $a,b$ 相同位置的 $p[i],s[j]$ 成一组存储，作为相异的键，值则为其数量)存储这样的 $p[i]$ 的值和 $s[j]$ 的值。再利用一点点前缀和后缀和，我们便可以用$O(n)$的时间分别遍历$i,j$的所有取值随后我们用两层循环遍历$pmp,smp$，将所有值的组合纳入答案由前面的观察，这个部分的时间复杂度是$O(\log^2n)$ 那么，我们处理每个区间的时间复杂度为： $O(n+\log^2n) = O(n)$ 这是一个分治算法，那么整体复杂度为 $O(n\log n)$，足以通过本题。