[CEOI 2021] Diversity多样性
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
[AdditionalFile3592.zip](file://AdditionalFile3592.zip?type=additional_file)
#3592. 「CEOI2021」多样性
标签: 传统 | 时间限制: 7000 ms | 内存限制: 512 MiB |
题目描述
题目译自 CEOI 2021 Day1 T1「Diversity」
我们称一个序列的多样性为这个序列中总共出现了多少种不同的数。称一个序列的总多样性为其所有连续子序列的多样性总和。
Zoran 有一个序列，他要对你进行 次独立的询问，在第 次询问中，他想知道对序列的第 到第 项构成的连续子序列经过重排后，能达到的总多样性的最小值是多少。
输入格式
第一行输入两个正整数 表示序列的长度和询问次数。
接下来一行 个数 ，表示这个序列。
接下来 行，每行两个整数 ，表示一个询问。
输出格式
输出 行，第 行输出对于第 个询问的回答。
样例 1
输入
3 1
1 2 3
1 3
输出
10
以任意顺序，每个连续子序列的多样性都等于它元素的个数。因此，对于询问的答案是 。
样例 2
输入
4 2
1 1 1 1
1 2
2 4
输出
3
6
以任意顺序，每个连续子序列的多样性都等于 。因此，对于每个询问，答案都是给定连续子序列的连续子序列数。
样例 3
输入
5 3
1 2 1 3 2
2 5
1 3
3 4
输出
16
8
4
对于第一个询问，一个最优顺序是 ，总多样性等于 。对于第二个询问，一个最优顺序是 ，总多样性等于 。对于第三个询问，一个最优顺序是 ，总多样性等于 。
数据范围与提示
| 子任务编号 | 附加限制 | 分值 |
|---|---|---|
| $1\le N\le 11,1\le a_i\le 3\times 10^5,Q=1,l_1=1,r_1=N$ | ||
| $1\le N\le 3\times 10^5,1\le a_i\le 11,Q=1,l_1=1,r_1=N$ | ||
| $1\le N\le 3\times 10^5,1\le a_i\le 23,Q=1,l_1=1,r_1=N$ | ||
| $1\le N\le 3\times 10^5,1\le a_i\le 10^3,Q=1,l_1=1,r_1=N$ | ||
| $1\le N\le 3\times 10^5,1\le a_i\le 3\times 10^5,Q=1,l_1=1,r_1=N$ | ||
| $1\le N\le 3\times 10^5,1\le a_i\le 3\times 10^5,1\le Q\le 5\times 10^4$ |