P11390 [COCI 2024/2025 #1] 教师 / Učiteljica
题目背景
译自 [COCI 2024/2025 #1](https://hsin.hr/coci/) T4。$\texttt{5s,0.5G}$。满分为 $120$。
题目描述
给定长度为 $n$ 的正整数序列 $a_1,a_2,\cdots,a_n$。给定常数 $k$。
求出满足以下条件的二元组 $(l,r)$ 的数量：
- $1\le l\le r\le n$；
- 对于任意 $1\le i\le k$，都存在一个数 $x$，使得 $x$ 在 $a_l,a_{l+1},\ldots,a_r$ 间出现**恰好** $i$ 次。
输入格式
第一行，两个正整数 $n,k$。
第二行，$n$ 个正整数 $a_1,a_2,\cdots,a_n$。
输出格式
输出一行一个整数，表示答案。
说明/提示
对于 $100\%$ 的数据，保证：
- $1\le n\le 10^5$；
- $1\le k\le 4$；
- $1\le a_i\le n$。
| 子任务编号 | $n\le$ | 特殊性质 | 得分 |
| :--: | :--: | :--: |:--: |
| $ 1 $ | $10^3$ | | $ 20 $ |
| $ 2 $ | $10^5$ | A | $ 15 $ |
| $ 3 $ | $10^5$ | B | $ 35 $ |
| $ 4 $ | $10^5$ | | $ 50 $ |
- 特殊性质 A：$1\le a_i\le k$。
- 特殊性质 B：$k=1$。