C

考虑计算每个中位数 (p_i) 的贡献：

• 对于 $(p_j > p_i)$ 令 $(a_j=1)$，对于 $(p_j<p_i)$ 令 $(a_j=-1)$。问题转化为统计满足 $(l\le i\le r)$ 且$[ \sum_{j=l}^{r} a_j = 0 ]$的区间 ([l,r]) 的个数。
• 从$(i)$往左扫描并累计和 $s_j=\sum_{k=j}^{i} a_k,$ 用一个计数数组记录各个取值的出现次数。
• 类似地，从 $(i)$ 往右扫描并累计和$t_j=\sum_{k=i}^{j} a_k,$询问取值为$(-t_j) 的 (s)$的数量并累加。
• 时间复杂度$(O(n^2))$。

D

注意到两类操作并不会改变单调性：对于任意 $x \le y$，在操作后仍然满足 $x' \le y'$。

将原序列升序排序，可以分别二分出最小和最大的下标。

时间复杂度 $O!\left(n \cdot \log \max |A_i|\right)$。

E

• 首先求出最短路，并构造最短路 DAG。
• 按照 $\text{dist}$排序，保留满足$d_u+w_{u,v}=d_v$ 的边 $u\to v$，成为 DAG。
• DAG 上 $1$ 到 $x$ 的路径，与原图 $1$ 到 $x$ 的最短路一一对应，转化为 DAG 上的问题。
• 恒等式：$$\sum_{j=1}^{n_i}\sum_{k=j+1}^{n_i}|d_{i,j}|\cdot|d_{i,k}| =\frac12\Bigg[\Big(\sum_{j=1}^{n_i}|d_{i,j}|\Big)^2-\sum_{j=1}^{n_i}|d_{i,j}|^2\Bigg]. $$
• 问题转化为求所有路径的长度和，以及路径长度平方和。
• 设 $(f_x,g_x,h_x)$分别表示所有从 $1$到 $x$ 的路径长度 $(0,1,2)$ 次方之和。则对边 $(y\to x)$：

$ f_x \mathrel{+}= f_y,\qquad g_x \mathrel{+}= g_y+f_y,\qquad h_x \mathrel{+}= h_y+2g_y+f_y. $