题解：CF2064F We Be Summing

这种题不太需要考虑去重的问题，如果能把所有合法的区间都表示为矩阵，那么就变成了矩阵加、数有多少个点大于 $0$，可以排序扫描线，用树状数组维护。

那么我们考虑如何把所有合法区间都表示为矩阵加的形式。首先我们可以去找每个子序列 $b[l,r]$ 的左右两个端点 $i,j$ 满足 $\min(a_l\sim a_i)+\max(a_{i+1}\sim a_r)=k,\min(a_l\sim a_{i-1})+\max(a_i\sim a_r)\neq k,\min(a_l\sim a_{j-1})+\max(a_j\sim a_r)=k,\min(a_l\sim a_j)+\max(a_{j+1}\sim a_r)\neq k$，然后我们可以去找到所有的 $[l,i]$，对于它们去找一个区间 $[l',r']$ 满足 $\forall t\in[l',r'],\min(a_l\sim a_i)+\max(a_{i+1}\sim a_t)=k$，那么矩阵 $[l,i][l',r']$ 就刻画了一堆合法的 $b$，关于 $j$ 的刻画是同理的。关于这个的实现，首先找 $[l,i]$ 我们可以按照 $a$ 从大到小加入所有位置，不妨设当前的值为 $x$，则我们找到每个 $x$ 结尾的最长区间使得这个区间的所有元素都 $\ge x$，就找到所有 $[l,i]$ 了。然后 $[l',r']$ 可以二分找，check 只需要一个静态的区间最值，用 st 表即可。总时间为 $O(n\log n)$。