*3300 的神仙题……思路是自己想出来了，但是漏洞百出，不得不借助题解……
首先你考虑枚举取出的子集大小 (s)。那么显然，若 (S) 中前 (s) 小的数的和为 (l)，前 (s) 大的数的和为 (r)，那么 (xin[l,r)) 都可以算。所以要求的就是对所有的 (s)，([l,r)) 的并的大小。
如何求并的大小？考虑像 SA 求本质不同子串个数那样，(suparrow) 地枚举区间 ([l,r))，每次算当前 ([l,r)) 中以前没被算过的。不难发现当 (suparrow) 时 (luparrow,ruparrow)，于是不难得出，要有重复的话，全部被上一个 (s) 给包了。于是我们只要求 (sum(r_i-l_i)-summax(0,r_i-l_{i+1}))。
求前面那个和式的话，需要支持插入删除地维护有序序列的前后缀和的区间和。插入删除不难想到平衡树，那么脑子中不难脑补出，维护前后缀和序列的平衡树在插入删除的时候，就是插入 / 删除一个新元素，然后把某段后缀整体加上某个值。然后要求区间和的话平衡树显然是可以做到的。
对后者怎么搞呢？你考虑那些 (r_i-l_{i+1}geq 0) 的做贡献，在这一题中有奇妙的性质：容易发现当 (suparrow) 时，(l_i) 增长的越来越快，(r_i) 增长的越来越慢，所以 (r_i-l_{i+1}) 是增长的越来越慢的，所以是一个单峰函数，浮在 (x)-axis 上的恰好是一段区间。怎么求这段区间呢？先三分（即对差分 / 导数二分）出极值点，然后往两边二分出左右端点。然后就是个前后缀和的区间和的事情了，用之前的平衡树恰好可以做到。于是这题就做完了……？
时间复杂度 2log（三分、二分 + 平衡树）。不过常数出奇的大，一是平衡树，二是每次一次三分两次二分，三是中间结果可能爆 ll（即使最终结果不会）要开 i128。所以就算是 3s TL 加上 CF 机子也跑不过去。这时候就不得不借助题解了/kel，然后发现我的思路全是不完善的地方。
- 平衡树。你维护的是一个有序数列，而不是普通数列，普通数列不满足单调性用平衡树维护，你这原序列、前后缀和序列都满足单调性，其实完全可以当成一个集合维护，一个值域线段树就够了。前后缀和序列也不用单独开线段树维护，这个是线段树节点内容易储存、更新的。并且离散化一下更好，这样常数会更小；
- 三分。这个单峰函数不仅是单峰函数，稍微想一下发现它还是镜像的…………于是极值点肯定在最中间，然后只往一边二分，另一边镜像过去并微调。这样就把 三分 * 1 + 二分 * 2 变成了 二分 * 1；
- i128。如果是 ull，那你会知道不用担心爆炸，最终结果不爆的话，中间运算的时候会在模意义下兜个圈子最终回到正确的结果。没想到 ll 也一样……那就只用 ll 存储了吧！
不愧是 *3300 的题啊……code