A. rng

有这样一个想法，我们把实数值域变成整数的。

具体来说就是把给每个区间的 $r_i$ 都减去 $1$。

这样的话期望就不难计算了：

以值域作为下标，修改就是每次把 $[l_i,r_i]$ 区间加上一个 $\frac{1}{r_i-l_i+1}$。

每次查询逆序对，其实就是求这个值： $\dfrac{\sum \limits_{i=l_i}^{r_i}(\frac{val_i}{2}+\sum \limits_{j=0}^{i-1} val_j)}{r_i-l_i+1}$

拆一下式子可以发现用线段树维护区间权值和、区间下标*权值和即可。

B. lg

因为求乘积的性质很好，可以考虑枚举最终的 $lcm$ 中出现了 $p^k$，然后再枚举 $gcd$ 的取值，然后求这样的方案数有多少个。

然后对于 gcd 显然是可以莫比乌斯反演的，还有一个限制是对于质因子 $p$，$p^k$ 必须出现并且不能出现 $p^{a},a>k$。

处理这个限制的方法是用至多去容斥，最大值为 $k$ 等价于 至多为 $k$ 减去 至多为 $k-1$。

然后 $[1,m]$ 之内满足 $p$ 质因子次数至多为 $k$ 并且是 $i$ 的倍数的数的个数就是 $\frac{m}{lcm(i,p^{k+1})}$。

然后写出来式子可以发现很多枚举是无意义的，有意义的有两种情况：

1.枚举的 $i$ 与 $p$ 互质，并且 $i*p \leq m$。

2.$i$ 与 $p$ 不互质。

前一种的复杂度可以用调和级数分析，后一种的复杂度可以用 $i$ 的质因子个数分析。

C. pm

考虑取出每个进行操作的区间，一定是长度为 $k$ 的区间用了 $k-1$ 次操作。

然后考虑求出来所有可能进行操作的区间，如果有了这些区间进行简单的区间不交的 dp 即可构造出方案。

然后对于可行区间，一定满足的性质是：

1.区间下标和值域同为 $[l,r]$。

2.区间内逆序对个数恰为 $r-l$。

枚举右端点 $r$，只要求出最大的合法的 $l$。

首先考虑找到满足第一个条件的 $l$，可以把第一个条件转化为：

区间内最大值等于 $r$ 并且区间内的 $\sum \limits_{i=l}^r a_i-i =0$。

考虑对 $a_i-i$作一个前缀和，后一个条件等价于两个前缀和相等，用 map 就可以查询。

然后只要区间查询最大值判断是否合法。如果不合法，那么显然使得 $l$ 更小也不可能合法。

对于第二个条件，问题是区间逆序对，但是有特殊性质：询问区间内的值域是连续的。

所以区间内与区间外的逆序对个数的形式是简单的，所以直接用 $[1,l-1]$ 前缀中大于 $r$ 的值的个数减一减就好了。 

至于构造方案，只要不断取出区间内最小的元素，然后把它放到序列最前面即可，因为每次都对应逆序对个数 $-1$，所以复杂度和正确性都是正确的。