题解 | #Number of Components#

考虑链上的联通块性质。

发现对于$f(l,r)f(l,r)$f(l,r)中，设一个联通块$[x,y][x,y]$[x,y]（位置），那么它一定满足$a_{x-1}\notin [l,r],a_{y+1}\notin [l,r],a_x\in [l,r],a_y\in [l,r]a\_\{x-1\}\notin [l,r],a\_\{y+1\}\notin [l,r],a\_x\in [l,r],a\_y\in [l,r]$ax−1​∈/​[l,r],ay+1​∈/​[l,r],ax​∈[l,r],ay​∈[l,r]。

于是我们只用数这个序列中有多少个相邻的位置使他们一个在区间里，一个不在，然后除以$22$2，就是联通块个数。

于是它$O\left(n^3\right)O(n^3)$O(n3)啦！

于是它$\text{TLE on test 9}\backslash text\{TLE\; on\; test\; 9\}$TLE on test 9啦。。。

然后我们发现，$ll$l固定时，对于一个相邻位置：

如果$a_i,a_{i+1}a\_i,a\_\{i+1\}$ai​,ai+1​都小于$ll$l，那扔掉。

否则如果有一个小于$ii$i，那就在$\max (a_i,a_{i+1})\backslash max(a\_i,a\_\{i+1\})$max(ai​,ai+1​)加入。

否则它只会在 $\min (a_i,a_{i+1})\backslash min(a\_i,a\_\{i+1\})$min(ai​,ai+1​) 的时候加入，在 $\max (a_i,a_{i+1})\backslash max(a\_i,a\_\{i+1\})$max(ai​,ai+1​) 时扔掉。

然后它$O\left(n^2\right)O(n^2)$O(n2)啦！

于是它$\text{TLE on test 11}\backslash text\{TLE\; on\; test\; 11\}$TLE on test 11啦。。。

于是我们稍微一分析，发现答案可以写成

${\sum }_{i=1}^n\frac{{\sum }_{j=0}^n[a_j,a_{j+1}\text{中有一个小于}i]\ast (n-\max (a\left[j\right],a[j+1])+1)}{2}\backslash sum\_\{i=1\}^n\backslash frac\{\backslash sum\_\{j=0\}^n[a\_j,a\_\{j+1\}\backslash text\{中有一个小于\}i]*(n-\backslash max(a[j],a[j+1])+1)\}\{2\}$∑i=1n​2∑j=0n​[aj​,aj+1​中有一个小于i]∗(n−max(a[j],a[j+1])+1)​

加上

${\sum }_{i=1}^n\frac{{\sum }_{j=0}^n[a_j,a_{j+1}\text{都大于i}]\ast \left(\right(n-\min \left(a\right[j],a[j+1\left]\right)+1)-(n-\max \left(a\right[j],a[j+1\left]\right)+1\left)\right)}{2}\backslash sum\_\{i=1\}^n\backslash frac\{\backslash sum\_\{j=0\}^n[a\_j,a\_\{j+1\}\backslash text\{都大于i\}]*((n-\backslash min(a[j],a[j+1])+1)-(n-\backslash max(a[j],a[j+1])+1))\}\{2\}$∑i=1n​2∑j=0n​[aj​,aj+1​都大于i]∗((n−min(a[j],a[j+1])+1)−(n−max(a[j],a[j+1])+1))​

然后发现每对相邻的数只会从下面的式子掉到上面的式子一次。

于是可以用一个优先队列维护在下面的相邻数对。

$O(n\log n)O(n\; \backslash log\; n)$O(nlogn)了。