#CS2428. 子数组的不同值
子数组的不同值
题目背景
翻译自 CSES-2428 题。
题目描述
给定一个由 n 个整数构成的数组，任务是计算数组中包含至多 k 个不同值的子数组的个数。
本题中子数组定义为：任意给定一个数组下标 l,r(1≤l≤r≤n)，得到的区间 [l,r]中的数组元素 al,al+1,⋯,ar。即可以理解成连续子序列。
输入格式
第一行输入两个整数 n 和 k，分别代表数组的大小和最多允许的不同值的个数。
第二行输入 n 个整数 x1,x2,...,xn，代表数组的值。
输出格式
输出一个整数，表示包含至多 k 个不同值的子数组的个数。
样例
5 2
1 2 3 1 1
10
说明/提示
1≤k≤n≤2⋅105,1≤xi≤109
