题意简述

长度为 $n$ 的街道，每个位置 $i$ 有法力水晶种类 $a_i$。

每个法师在位置 $p$，喜欢的水晶种类区间 $[l, r]$。

需要收集所有在街道上存在且法师喜欢的种类，每个种类只需一个。

法力消耗 = 所选水晶位置到 $p$ 的距离之和。

求最小总消耗。

关键观察

对每个种类 $t \in [l, r]$，如果街道上有多个位置有该种类，我们应选择离 $p$ 最近的那个，这样消耗最小。

因此问题转化为： 对 $t \in [l, r]$ 且 $t$ 在街道上出现，求 $\min_{i: a_i = t} |i - p|$，然后求和。

问题难点

直接枚举种类会超时（$n,q$ 最大 $2\times 10^5$，种类区间可能很大）。

需要快速找出在 $[l, r]$ 内且实际在街道上出现过的种类，并求最小距离。

思路

预处理

对每个种类 $t$，记录它在街道上出现的所有位置（按坐标排序）。

查询处理

对于查询 $(p, l, r)$：

我们只关心在 $[l, r]$ 内且街道上出现过的种类。

对每个这样的种类 $t$，在它的位置列表中二分查找离 $p$ 最近的位置，计算距离 $d_t$。

答案 = $\sum d_t$。

但这样仍然可能超时，因为种类区间内实际出现的种类数可能很多。

优化

注意到位置是 1 到 n，我们可以换个角度：

对每个位置 $i$，它提供种类 $a_i$，且它到 $p$ 的距离是 $|i-p|$。

我们想要：对每个在 $[l, r]$ 内的种类，取它所有位置中距离 $p$ 最小的。

这相当于： 对每个种类 $t \in [l, r]$，取 $\min{|i-p| : a_i = t}$ 求和。

更高效的方法

我们可以离线处理：

把查询按 $p$ 排序（或者分治？）。

用数据结构维护当前“最近位置”信息。

但这里有一个经典做法： 只考虑每个种类在 $p$ 左边最近的和右边最近的位置，因为最小距离一定来自左边最近或右边最近的出现位置。

最终算法框架

对每个种类 $t$，记录所有出现位置（有序列表）。

对查询 $(p, l, r)$：

初始化答案 = 0

对 $t$ 从 $l$ 到 $r$：

如果 $t$ 在街道上出现过：

在 $t$ 的位置列表中二分找到 $\ge p$ 的第一个位置，得到右边最近位置 $R$

左边最近位置 $L$ 就是 $R$ 的前一个（如果存在）

计算 $\min(|L-p|, |R-p|)$ 并累加

输出答案

但这样最坏 $O(nq)$ 会超时。

正解思路（莫队 + 平衡树/分块）

实际上，这个问题是 区间种类最小距离查询，比较复杂。 一种可行方法：

把“种类”看作“颜色”，问题变成：区间 $[l, r]$ 内所有颜色，求它们到 $p$ 的最小距离之和。

可以按 $p$ 排序查询，用双向链表维护每个颜色的最近出现位置，用树状数组/线段树维护距离和。

但实现较复杂。

简单可行方案（针对部分分）

对于 $n,q \le 2000$ 可以直接暴力：

对每个查询，枚举所有位置 $i$，如果 $a_i \in [l, r]$，则更新种类 $a_i$ 的最小距离。

然后累加。

对于 $a_i = i$（种类=位置）的情况：

那么 $[l, r]$ 内存在的种类就是 $[l, r]$ 本身。

每个种类 $t$ 的最小距离就是 $|t - p|$。

答案 = $\sum_{t=l}^r |t-p|$，可以 $O(1)$ 公式计算。

对于 $l=1, r=n$：

所有种类都存在，答案 = $\sum_{t=1}^n \min_{i:a_i=t} |i-p|$，可以预处理。

总结

本题是较难的区间种类查询问题，需要复杂数据结构（莫队/分块/线段树+预处理最近位置）才能 AC 全部数据。 核心是快速求区间内各颜色到某点的最小距离和。