agc037_f Counting of Subarrays
https://atcoder.jp/contests/agc037/tasks/agc037_f
https://img.atcoder.jp/agc037/editorial.pdf
Tutorial
我们称一个序列为合法序列当且仅当存一个 (K) 使得它是 ((K,L)) 的
考虑如何判断一个序列 ((A_1,A_2, cdots , A_N)) 是否合法, 假如 (N=1) , 那么它是合法的,否则
- 判断如果整个序列相等,那么当 (N ge L) 时, 序列合法
- 否则, 设 (m) 为 (A) 中最小的数, 令 ([l_1,r_1] cup cdots cup [l_k, r_k]) 为 (A) 中值为 (m) 的元素的位置集合((r_i+1<l_{i+1}))
- 如果存在一个区间 ([l_i,r_i]) 的大小 (<L) , 那么这不是一个合法序列
- 否则, 对于每个区间 ([l_i,r_i]) 将其替换为 ([dfrac {r_i - l_i + 1}L]) 个 (m+1) , 回到第一步重新判断.
如果直接这样判断, 我们用set维护元素的位置集合, 那么每次新增加一个元素时需要删除 (L) 个元素, 复杂度为 (O(N log N))
回到原本的问题, 如何统计有多少连续子序列是合法序列, 注意如果 (Y) 是 (X) 的连续子序列, 那么我们在对 (Y) 进行上面的判断步骤时, 中间部分的序列也是 (X) 中间部分的子序列, 所以我们对整个序列进行如上的判断, 需要考虑如何计算.
我们将这个问题描述为, 给出 (L_1, cdots, L_n, R_1, cdots, R_n) , 对于所有合法子序列 (A_i, cdots A_j) 计算 (L_iR_j) 的和.
- 如果整个序列的元素相等, 答案为所有满足 (i = j) 或 (j-i+1 ge L) 的 ((i,j)) 的 (L_iR_j) 的和, 这部分可以线性计算
- 否则与上面类似的定义 (m) 和 (l_1,r_1 , cdots l_k,r_k)
- 对于每个 (i) 考虑 ([l_i,r_i]) 中的合法子序列 ([p,q]) 的 (L_p,R_q) 的和
- 对于每个 (i) , 替换 ([l_i,r_i]) 为 ([dfrac {r_i-l_i+1}L]) 个 (m+1) 与适当的一些 (L,R)
- 递归对其计算
考虑如何确定新的 (L,R) , 利用下面的例子感性理解一下
注意我们新加入的区间里的子区间的答案在这一层已经统计过了,需要减去
复杂度 (O(N log N))