题解：CF2064F We Be Summing

Judgelight · 2025-02-25 23:00:07 · 题解

传送门

这种题不太需要考虑去重的问题，如果能把所有合法的区间都表示为矩阵，那么就变成了矩阵加、数有多少个点大于 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)。