给定序列 {an}\{a_n\}{an} 和 kkk,求有多少子区间 [l,r][l,r][l,r] 满足 mex{al,al+1,…,ar−1,ar}+min{al,al+1,…,ar−1,ar}+k≥max{al,al+1,…,ar−1,ar}\operatorname{mex}\{a_l,a_{l+1},\dots,a_{r-1},a_r\}+\min\{a_l,a_{l+1},\dots,a_{r-1},a_r\}+k\geq \max\{a_l,a_{l+1},\dots,a_{r-1},a_r\}mex{al,al+1,…,ar−1,ar}+min{al,al+1,…,ar−1,ar}+k≥max{al,al+1,…,ar−1,ar}。
mex\operatorname{mex}mex 定义为集合内没有出现过的最小的非负整数。
第一行两个整数 n,kn,kn,k(1≤n≤5×105,0≤k≤n1\leq n\leq 5\times 10^5,0\leq k\leq n1≤n≤5×105,0≤k≤n)。
第二行 nnn 个非负整数,第 iii 个表示 aia_iai(0≤ai≤n0\leq a_i\leq n0≤ai≤n)。
一行一个数,表示满足条件的子区间个数。
3 0 1 0 2
5
注册一个 云斗学院 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 云斗学院 通用账户