#P16101. [Oni2016]Calafat

    ID: 15312 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 5 上传者: 标签>CF1800普及+/提高-差分转化离线查询扫描中维护贡献树状数组

[Oni2016]Calafat

题目描述

给定一个长度为 NN 的自然数序列 a1,a2,…,aNa_1,a_2,\ldots,a_N。

对于一个子区间 [st,dr][st,dr],考虑其中出现过的每种不同数值 xx。若 xx 在该区间中的第一次出现位置为 LxL_x,最后一次出现位置为 RxR_x,则它对答案的贡献为:

Rx−Lx.R_x-L_x.

若 xx 在区间中只出现一次,则贡献为 00。

对于每个询问区间 [st,dr][st,dr],请输出所有不同数值贡献之和:

∑x(Rx−Lx).\sum_x (R_x-L_x).

输入格式

第一行包含两个整数 N,MN,M,表示序列长度和询问数量。

第二行包含 NN 个整数,表示给定序列。

接下来 MM 行,每行包含两个整数 st,drst,dr,表示一个询问区间。

输出格式

输出 MM 行,第 ii 行表示第 ii 个询问的答案。

数据范围

  • 1≤N,M≤2000001\le N,M\le 200000;
  • 1≤st≤dr≤N1\le st\le dr\le N;
  • 1≤ai≤N1\le a_i\le N;
  • 约 20%20\% 的测试满足 N,M≤1000N,M\le 1000;
  • 约 25%25\% 的测试满足 N,M≤35000N,M\le 35000,且序列中不同数值个数最多为 100100;
  • 约 25%25\% 的测试满足 N,M≤70000N,M\le 70000。

样例

输入

7 3
1 3 1 2 2 1 3
2 4
2 7
3 6

输出

0
9
4

样例解释

区间 [2,4][2,4] 中每种数值都只出现一次,所以答案为 00。

区间 [2,7][2,7] 中:

  • 33 出现在位置 2,72,7,贡献 55;
  • 11 出现在位置 3,63,6,贡献 33;
  • 22 出现在位置 4,54,5,贡献 11。

总和为 99。

区间 [3,6][3,6] 中,11 的贡献为 33,22 的贡献为 11,总和为 44。