「CEOI2021」多样性

ID: 16731

传统题

7000ms

512MiB

难度: (无)

上传者:

标签>

贪心

分块及按大小分类

莫队

CEOI

2021

题目描述

题目译自 CEOI 2021 Day1 T1「Diversity」

我们称一个序列的多样性为这个序列中总共出现了多少种不同的数。称一个序列的总多样性为其所有连续子序列的多样性总和。

Zoran 有一个序列，他要对你进行 $Q$ 次独立的询问，在第 $i$ 次询问中，他想知道对序列的第 $l_i$ 到第 $r_i$ 项构成的连续子序列经过重排后，能达到的总多样性的最小值是多少。

第一行输入两个正整数 $N,Q$ 表示序列的长度和询问次数。

接下来一行 $N$ 个数 $a_1,a_2,\ldots,a_N$ ，表示这个序列。

接下来 $Q$ 行，每行两个整数 $l_i,r_i$ ，表示一个询问。

输出 $Q$ 行，第 $i$ 行输出对于第 $i$ 个询问的回答。

3 1
1 2 3
1 3

3
6

16
8
4

子任务编号	附加限制	分值
$1$	$1\le N\le 11,1\le a_i\le 3\times 10^5,Q=1,l_1=1,r_1=N$	$4$
$2$	$1\le N\le 3\times 10^5,1\le a_i\le 11,Q=1,l_1=1,r_1=N$	$10$
$3$	$1\le N\le 3\times 10^5,1\le a_i\le 23,Q=1,l_1=1,r_1=N$	$8$
$4$	$1\le N\le 3\times 10^5,1\le a_i\le 10^3,Q=1,l_1=1,r_1=N$	$16$
$5$	$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$	$26$
$6$	$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$	$36$