← 返回题目列表

AtCoder · agc037_f

F. 子数组的计数

中文机器翻译题面 查看原题

分数: 1800 点

问题陈述

对于序列 S 正整数和正整数 k 和 l, S 据说属于 级别 (k,l) 当满足以下条件之一时:

  • 的长度 S is 1,其唯一元素是 k.
  • 存在序列 T_1,T_2,...,T_m (m \geq l) 属于级别 (k-1,l) 这样的串联 T_1,T_2,...,T_m 按此顺序与 S.

请注意,当 k=1,即序列属于级别 (1,l) 仅当第一个条件满足时。

给定一个正整数序列 A_1,A_2,...,A_N 和一个正整数 L。 查找子序列的数量 A_i,A_{i+1},...,A_j (1 \leq i \leq j \leq N) 满足以下条件:

  • 存在一个正整数 K 这样的序列 A_i,A_{i+1},...,A_j 属于级别 (K,L).

约束

  • 1 \leq N \leq 2 \times 10^5
  • 2 \leq L \leq N
  • 1 \leq A_i \leq 10^9

输入

输入由标准输入按以下格式给出:

N L
A_1 A_2 ... A_N

输出

打印子序列的数量 A_i,A_{i+1},...,A_j (1 \leq i \leq j \leq N) 满足条件。


示例输入 1

9 3
2 1 1 1 1 1 1 2 3

示例输出 1

22

例如,两个序列 (1,1,1) 和 (2) 属于级别 (2,3),所以序列 (2,1,1,1,1,1,1) 属于级别 (3,3).


示例输入 2

9 2
2 1 1 1 1 1 1 2 3

示例输出 2

41

示例输入 3

15 3
4 3 2 1 1 1 2 3 2 2 1 1 1 2 2

示例输出 3

31