C. [R57C]RhythmName

Type: Default

1000ms

512MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

汗水浇灌的跑道不会说话，但时间会给出回答。

某市举办了一场马拉松比赛，共有 $n$ 位选手完成比赛，他们的最终成绩均以整数秒为单位记录。第 $i$ 位选手的成绩为 $t_i$ 。

为了对比赛成绩进行分层统计，主办方设置了 $q$ 个查询。每个查询给定一个时间区间 $[l_i, r_i]$ ，你需要统计所有成绩落在该区间内的选手成绩所对应的“合理值” $^{\dagger}$ 。若该区间内不存在任何选手成绩，则输出 $0$ 。

$^{\dagger}$ :对于一次查询给定的时间区间 $[l, r]$ ，设所有满足 $l \le t_i \le r$ 的成绩按任意顺序组成数组

x_1, x_2, \dots, x_m

其中 $m$ 表示满足条件的成绩个数。那么该查询的“合理值”定义为

(x_1-l)^2 + (x_2-l)^2 + \cdots + (x_m-l)^2

第一行包含两个正整数 $n, q$ ，分别表示参赛选手的数量和查询次数。

第二行包含 $n$ 个非负整数 $t_1, t_2, \dots, t_n$ ，依次表示每位选手的完赛时间。

接下来的 $q$ 行，每行包含两个非负整数 $l_i, r_i$ ，表示一次查询的时间区间。

输出 $q$ 行，每行一个整数表示该询问的合理值。

6 4
3 1 4 1 5 9
1 9
2 6
0 0
4 9

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n,q \le$
$1$	$50$	$5000$
$2$	$50$	$2 \times 10^5$

对于 $100\%$ 的数据，保证 $1\le n,q\le 2 \times 10^5,0\le t_i,l_i,r_i\le 10^4,l_i\le r_i$。