帮帮蒟蒻吧QaQ

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 3e5 + 10;
int n, q, len;
long long t[maxn], ans;
pair <pair<int, int>, int> que[maxn]; //存储提问（依次存储右端点、左端点、编号）
pair <int, int> num[maxn], seg[2 * maxn]; // num 存储数列，seg 存储提问（依次存储右端点、左端点）
int lowbit(int x) {
	return x & -x;
}
void update(int x) {
	if (x > n) return;
	t[x] ++;
	update(x + lowbit(x));
}
long long get_sum(int x) {
	if (x < 1) return 0;
	return t[x] + get_sum(x - lowbit(x));
}
pair <int, int> buildseg(int x, int y) { // 建立线段
	return {max(x, y), min(x, y)};
}
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &num[i].first);	
		num[i].second = i;
	}
	sort(num + 1, num + 1 + n);
	for (int i = 1; i <= n; i++) {
		if (n == 1) break; //特判
		int ssn = num[i + 1].second,sst = num[i].second, ssb = num[i - 1].second;
		int sfn = num[i + 1].first, sft = num[i].first, sfb = num[i - 1].first;
		if (i == 1) seg[++len] = buildseg(sst, ssn);
		else if (i == n) seg[++len] = buildseg(ssb, sst);
		else{
			if (sft - sfb >= sfn - sft) seg[++len] = buildseg(ssn, sst);
			if (sft - sfb <= sfn - sft) seg[++len] = buildseg(sst, ssb);
		}
	}
	if (len) sort(seg + 1, seg + 1 + len);
	for (int i = 1; i <= q; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		que[i] = {{r, l}, i};
	}
	sort(que + 1, que + 1 + q); // 提问先排序
	int p = 0;
	for (int i = 1; i <= n; i++) {
		while (seg[p].first <= que[i].first.first && p < len) update(seg[++p].second);
		// 加入已被覆盖的线段
		ans += (long long)(p - get_sum(que[i].first.second - 1)) * que[i].second;//统计答案
	}
	printf("%lld", ans);
}