题意
给定一个数列 $a_1, a_2, \cdots, a_n$.
定义在有序数对 $(x, y)$ 上的“好对”：对于 $a_x$，$y\in[1, x)\cup(x, n]$ 能使 $|a_x-a_y|$ 取最小值。
给定 $q\leq 3\times 10^5$ 组询问，每次询问一个区间 $[l, r]$ 中，有多少个好对。
题目求：每次询问的答案 $Ans_i$ 与询问编号 $i$ 的乘积的和，即：
\sum_{i=1}^{m}Ans_i\times i
$$
分析
关于匹配
任何一个好对 $(x, y)$，都满足 $|a_x-a_y|\leq |a_x-a_i|(i\neq x)$.
并且通过数据范围可以发现：$\forall i\neq j$ 都有 $a_i\neq a_j$，所以当 $x$ 固定时，确定 $y$ 的方法是非常自然的。
将 $a$ 数组排序，排序后的数组为 $b$，不妨设 $a_x$ 在 $b$ 中的下标为 $t$，那么 $a_y$ 在 $b$ 中的下标只可能为 $t-1$ 和 $t+1$.
具体地：
- 如果 $|b_t-b_{t-1}|<|b_{t+1}-b_{t}|$，也就是 $b_{t-1}$ 距离 $b_t$ 更近，那么 $a_y$ 在 $b$ 中的下标为 $t-1$；
- 如果 $|b_t-b_{t-1}|>|b_{t+1}-b_{t}|$，此时 $b_{t+1}$ 距离 $b_t$ 最近，$a_y$ 在 $b$ 中的下标为 $t+1$；
- 如果 $|b_t-b_{t-1}|=|b_{t+1}-b_{t}|$，$a_y$ 在 $b$ 中的下标为 $t-1$ 或 $t+1$.
总之，我们可以非常容易地在 $O(n\log n)$ 复杂度内，对于每个 $x$，找到能与其构成好的配对的 $y$.
关于询问
思路
现在的问题是如何统计答案。
因为题目只要求输出所有询问的和，于是想到将询问离线下来。对于每个好对，统计有多少个询问完全覆盖了它。这个好对对于最终答案的贡献就是：所有覆盖它的询问的编号之和。
对于这个问题，容易想到将所有询问排序，之后用树状数组维护，具体方法：
方法
从左到右枚举 $[1, n]$，假设枚举到了 $i$.
对于 $i$，我们已经计算过与其匹配的数，在 $a$ 中的下标 $y$，如果 $y>i$，那么所有左端点 $l\leq i$ 且右端点 $r\geq y$ 的询问都能包含这个好对。
再考虑答案的形式 $\sum_{i=1}^{m}Ans_i\times i$，我们现在要求：左端点 $l\leq i$ 且右端点 $r\geq y$ 的询问的编号和，使用树状数组维护。
于是考虑将询问按照左端点排序，在枚举到 $i$ 的时候，把所有左端点 $l\leq i$ 的询问加入到树状数组中，把树状数组的位置 $r$ 的权值加上这个询问的编号 $num$.
这样，$(i, y)$ 的贡献就等价于：树状数组中 $[y, n]$ 的区间和。
如果与 $i$ 匹配的 $y < i$，在上面的方法中并没有包含到。所以我们再反向枚举一遍 $i$，方法相同。将右端点 $r\geq i$ 的询问加入树状数组，每次的贡献为树状数组中 $[1, y]$ 的区间和。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 3e5 + 10;
const int inf = 0x3f3f3f3f3f3f3f3f;
int c[MAXN];
int n, m;
int lowbit(int x) {
return x & (-x);
}
void update(int x, int k) {
for(int i = x; i <= n; i += lowbit(i)) {
c[i] += k;
}
}
int query(int x) {
int ret = 0;
for(int i = x; i > 0; i -= lowbit(i)) {
ret += c[i];
}
return ret;
}
int query2(int x) {
return query(n) - query(x - 1);
}
int a[MAXN];
struct Node{int num, val;} b[MAXN];
bool cmp(Node A, Node B) {
return A.val <= B.val;
}
struct Query{int val, l, r;} q[MAXN];
bool cmp2(Query A, Query B) {
return A.r >= B.r;
}
bool cmp3(Query A, Query B) {
return A.l <= B.l;
}
int rk[MAXN];
signed main() {
scanf("%lld%lld", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
b[i].val = a[i]; b[i].num = i;
}
sort(b + 1, b + n + 1, cmp);
for(int i = 1; i <= n; i++) {
rk[b[i].num] = i;
}
for(int i = 1; i <= m; i++) {
q[i].val = i;
scanf("%lld%lld", &q[i].l, &q[i].r);
}
sort(q + 1, q + m + 1, cmp2);
int ans = 0;
b[0].val = -inf; b[n + 1].val = inf;
for(int i = n, j = 1; i >= 1; i--) {
while(q[j].r >= i && j <= m) {
update(q[j].l, q[j].val);
j++;
}
//下面六行：判断 t-1 和 t+1，哪个距离 t 更近，能与 t 构成好的匹配。
if(b[rk[i]].val - b[rk[i] - 1].val <= b[rk[i] + 1].val - b[rk[i]].val) {
if(b[rk[i] - 1].num < i) ans += query(b[rk[i] - 1].num);
}
if(b[rk[i]].val - b[rk[i] - 1].val >= b[rk[i] + 1].val - b[rk[i]].val) {
if(b[rk[i] + 1].num < i) ans += query(b[rk[i] + 1].num);
}
}
sort(q + 1, q + m + 1, cmp3);
memset(c, 0, sizeof(c));
for(int i = 1, j = 1; i <= n; i++) {
while(q[j].l <= i && j <= m) {
update(q[j].r, q[j].val);
j++;
}
if(b[rk[i]].val - b[rk[i] - 1].val <= b[rk[i] + 1].val - b[rk[i]].val) {
if(b[rk[i] - 1].num > i) ans += query2(b[rk[i] - 1].num);
}
if(b[rk[i]].val - b[rk[i] - 1].val >= b[rk[i] + 1].val - b[rk[i]].val) {
if(b[rk[i] + 1].num > i) ans += query2(b[rk[i] + 1].num);
}
}
cout << ans << endl;
return 0;
}