题意：给一个序列，问\(\sum_{1 \le l \le r \le n}f(l,r)\)。

其中\(f(l,r)\)表示把\(a_{l..r}\)排序后每一个数乘上其排名的和。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路：肯定是考虑每个数乘上的系数啊。

那么我们可以把序列分两类，一类是以\(a_i\)为开头的，另一类是以其为结尾的。

然后看以\(a_i\)为开头的序列中\(a_i\)的排名变化情况。

那么我们从左向右扫描，假设现在遇到了\(a_i\)，那么其之前所有比它大的（即\(a_i+1...N\)）的排名都会加\(1\)，并且这个会保持\(n-i+1\)个序列。并且\(a_i\)自己也会有一个\(1\)的排名。所以我们需要将\(a_i...N\)加上\(n-i+1\)。果断线段树。

但是我们并没有方法处理“在\(a_i\)之前”的内容，所以我们直接把所有的都加上\(n-i+1\)，到了\(a_i\)的第一次出现时清\(0\)就好了。

那么现在我们求出了所有的\(a_i\)向左向右的序列中\(a_i\)的排名。我们还得把它们合并起来。

对于每一个\(1 \le l \le i \le r \le n\)，我们都有\(rank_{a_i}=rank_{(l,i),a_i}+rank_{(i,r),a_i}-1\)。所以我们就是要求\(\sum_{l \le i}rank_{(l,i),a_i}\times (n-i+1)+\sum_{i \le r}rank_{(i,r),a_i}\times i-(n-i+1)\times i\)。

注意取模 ！！！

我就是因为在把\(a_i\)的\(rank\)和清\(0\)的时候写了个负数进去而\(wa\)了一次。。。

还有一次\(wa\)是因为我竟然把左右两个和乘起来了。。。

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄