该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P11390 [COCI 2024/2025 #1] 教师 / Učiteljica

题目背景

译自 COCI 2024/2025 #1 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$。

输出格式

输出一行一个整数，表示答案。

输入输出样例 #1

输入 #1

3 1
1 2 1

输出 #1

6

输入输出样例 #2

输入 #2

6 3
6 5 6 4 5 5

输出 #2

1

输入输出样例 #3

输入 #3

6 2
5 4 5 2 6 5

输出 #3

5

说明/提示

对于 $100\%$ 的数据，保证：

• $1\le n\le 10^5$；
• $1\le k\le 4$；
• $1\le a_i\le n$。

• 特殊性质 A：$1\le a_i\le k$。
• 特殊性质 B：$k=1$。

#5696. 「COCI 2024/2025 #1」Učiteljica

标签: 传统 | 时间限制: 5000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #1 T4「Učiteljica」

在 Varaždin 最好的学校里，有一位出色的计算机科学老师，她以有趣而不寻常的想法而闻名。她的名字叫 Lana，经常给学生出一些看似不可能或无法解决的问题。每个学生在一学年内只需要解决 $1$ 个问题就能以优异的成绩通过课程。到年底没有解决任何任务的学生将不得不留级。在学期的最后一天，她在黑板上写下了一个极其困难的问题，内容如下：

想象你有一个长度为 $N$ 的数字序列，你可以从开头或结尾（或两者）移除一些元素。问有多少种执行此类删除的方式，使得删除后，至少存在 $1$ 个数字出现恰好 $1$ 次，至少存在 $1$ 个数字出现恰好 $2$ 次，……，并且至少存在 $1$ 个数字出现恰好 $K$ 次。

一个名叫 Fran 的学生，此前还没解决过任何问题，很快说道：「我知道怎么解决这个问题。」Lana 老师不相信 Fran，告诉他：「在接下来的 $30$ 分钟内写出代码，我就相信你。如果你做不到，你就得留级。」Fran 不会编程，所以他紧急请求你的帮助来写出解决此任务的代码。在匆忙中，他忘记解释他解决任务的想法了。请编写一个程序，输入 $N$ 和 $K$ 以及那 $N$ 个元素的序列，来解决 Lana 的问题以帮助 Fran。

输入格式

第一行包含 $2$ 个正整数 $N$ $(1 \leq N \leq 10^{5})$ 和 $K$ $(1 \leq K \leq 4)$。

第二行包含 $N$ 个正整数 $a_{i}$ $(1 \leq a_{i} \leq N)$，即题目描述中的数字。

输出格式

在第一行，输出一个整数，即满足任务条件的删除方式数量。如果两个删除方式在某个位置的元素一个被删除而另一个未被删除，则认为这两种删除方式不同。

样例 1

输入

3 1
1 2 1

输出

6

删除后的可能序列有：$[1], [2], [1], [1, 2], [2, 1], [1, 2, 1]$，在每一个序列中，都有一个数字恰好出现了 $1$ 次。

样例 2

输入

6 3
6 5 6 4 5 5

输出

1

删除后，满足至少有 $1$ 个数字出现 $1$ 次、至少有 $1$ 个数字出现 $2$ 次的序列只有原序列本身。

样例 3

输入

6 2
5 4 5 2 6 5

输出

5

数据范围与提示

详细子任务附加限制及分值如下表所示。