这是本文档旧的修订版！
题解
A. 序列
题意
给定一个 $1\sim n$ 的排列 $a$，该排列的每个子序列 $s=(s_1,s_2\cdot s_p)$ 对 $k$ 的贡献为 $\sum_{i=1}^{p-1}[s_i\lt k\lt s_{i+1}]+[s_i\gt k\gt s_{i+1}]$。
对 $k=1\sim n$，问所有子序列对 $k$ 的贡献总和。
题解
考虑所有子序列中 $(a_i,a_j)(i\lt j)$ 相邻的情况，易知共有 $2^{n-j+i+1}$ 个子序列满足条件。
于是 $(a_i,a_j)(i\lt j)$ 对 $k\in (\min(a_i,a_j),\max(a_i,a_j))$ 的贡献为 $2^{n-j+i+1}$，考虑枚举 $(i,j)$ 然后差分计算贡献，于是得到 $O(n^2)$ 暴力做法。
接下来考虑优化，不妨假设每对 $(a_i,a_j)(i\lt j)$ 对所有 $k$ 产生 $2^{n-j+i+1}$ 的正贡献，然后对 $k\in [1,\min(a_i,a_j)]\bigcup [\max(a_i,a_j),n]$ 产生负贡献。
正贡献总和不难发现为 $\sum_{i=1}^{n-1} (n-i)2^{n-i-1}$ ，接下来考虑计算负贡献总和。
考虑从 $1\sim n$ 枚举 $j$，树状数组维护 $c_{a_i}=2^ia_i(i\lt j)$，于是 $j$ 对 $[1,a_j]$ 产生负贡献为 $2^{n-j}\sum_{i=1}^{a_j} c_i$，对 $[a_j,n]$ 产生负贡献为 $2^{n-j}\sum_{i=a_j}^{n} c_i$。
同理，再从 $n\sim 1$ 枚举 $i$ 计算负贡献。最后用正贡献总和减去负贡献总和即可得到答案，时间复杂度 $O(n\log n)$。
赛后总结
jxm：感觉有一半的时间在 debug
