#P5710. [CEOI2021] Diversity

    ID: 4711 传统题 7000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-贡献法排序贪心交换论证普通莫队奇偶块排序链表增量维护等差数列求和

[CEOI2021] Diversity

题目背景

译自 CEOI2021 Day1 T1. Diversity。

题目描述

定义一个序列的 多样性 为其不同的元素个数,一个序列的 总多样性 为其所有子区间的 多样性 的和。

例如,序列 (1,1,2)(1,1,2) 的 多样性 为 22 ,因为其有两种元素;它的 总多样性 为序列 (1),(1),(2),(1,1),(1,2),(1,1,2)(1),(1),(2),(1,1),(1,2),(1,1,2) 的 多样性 之和,即 1+1+1+1+2+2=81+1+1+1+2+2=8。

给出长为 NN 的序列 {ai}\{a _i\} 与 QQ 个互相独立的询问,每个询问给出 [l,r][l,r]。求将原序列 [l,r][l,r] 内的数重排可以得到的该区间最小的 总多样性。

输入格式

输入第一行包含两个整数 NN 和 QQ,表示序列长度和询问数量。

第二行 NN 个整数,表示序列 {ai}\{a_i\}。

接下来 QQ 行,每行两个整数 li,ril_i,r_i,表示第 ii 次询问的区间。

输出格式

输出应包含 QQ 行整数,第 ii 行的整数表示第 ii 个询问的答案。

样例 #1

样例输入 #1

3 1
1 2 3
1 3

样例输出 #1

10

样例 #2

样例输入 #2

4 2
1 1 1 1
1 2
2 4

样例输出 #2

3
6

样例 #3

样例输入 #3

5 3
1 2 1 3 2
2 5
1 3
3 4

样例输出 #3

16
8
4

提示

样例解释

对于第一组样例,无论怎样重排,询问区间的 总多样性 总是 1010。

对于第二组样例,序列所有元素都为 11,故无需重排。区间 [1,2][1,2] 的 总多样性 为 33,区间 [2,4][2,4] 的 总多样性 为 66。

对于第三组样例,第一个询问可将序列重排为 (1,2,2,3)(1,2,2,3),它的 总多样性 为 1+1+1+1+2+1+2+2+2+3=161+1+1+1+2+1+2+2+2+3=16;第二个询问可将序列重排为 (1,1,2)(1,1,2),它的 总多样性 为 1+1+1+1+2+2=81+1+1+1+2+2=8;第三个询问可将序列重排为 (1,3)(1,3),它的 总多样性 为 1+1+2=41+1+2=4。

子任务

所有测试点均满足 1≤N≤3×1051\leq N\leq 3\times 10^5,1≤ai≤3×1051\leq a_i\leq 3\times 10^5,1≤Q≤5×1041\leq Q\leq 5\times 10^4。

各子任务的约束条件如下:

子任务编号 分值 约束
11 44 1≤N≤111\leq N\leq 11,1≤ai≤3×1051\leq a_i\leq 3\times 10^5,Q=1Q=1,l1=1l_1=1,r1=Nr_1=N
22 1010 1≤N≤3×1051\leq N\leq 3\times 10^5,1≤ai≤111\leq a_i\leq 11,Q=1Q=1,l1=1l_1=1,r1=Nr_1=N
33 88 1≤N≤3×1051\leq N\leq 3\times 10^5,1≤ai≤231\leq a_i\leq 23,Q=1Q=1,l1=1l_1=1,r1=Nr_1=N
44 1616 1≤N≤3×1051\leq N\leq 3\times 10^5,1≤ai≤10001\leq a_i\leq 1000,Q=1Q=1,l1=1l_1=1,r1=Nr_1=N
55 2626 1≤N≤3×1051\leq N\leq 3\times 10^5,1≤ai≤3×1051\leq a_i\leq 3\times 10^5,Q=1Q=1,l1=1l_1=1,r1=Nr_1=N
66 3636 1≤N≤3×1051\leq N\leq 3\times 10^5,1≤ai≤3×1051\leq a_i\leq 3\times 10^5,1≤Q≤5×1041\leq Q\leq 5\times 10^4