L 区间与绝对值

用莫队先离线操作，用树状数组维护两个东西，一个是小于（大于）一个数的个数和小于（大于）一个数的和，那我们每次加入一个数时产生的贡献时 （） ，删除一个数时时我们对应删除掉即可。我们这样只维护了一半，乘2即是答案。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define sz(x) x.size()
#define lbt(x) (x)&(-x)
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

typedef pair<int, int> PII;
typedef double db;
const int N = 1e5 + 10, mod = 998244353, inf = 0x3f3f3f3f;
const db EPS = 1e-9;
int res[N], a[N], id[N], cnt[N], t[2][N];
struct Q {
	int l, r, k;
}q[N];
int tmp;
void add(int c, int x, int v) {
	while (x < N) {
		t[c][x] += v;
		x += lbt(x);
	}
}
int query(int c, int x) {
	int res = 0;
	while (x > 0) {
		res += t[c][x];
		x -= lbt(x);
	}
	return res;
}

void add(int x) {
	x = a[x];
	tmp += query(0, x - 1) * x - query(1, x - 1);
	tmp += (query(1, N - 1) - query(1, x)) - (query(0, N - 1) - query(0, x)) * x;
	add(0, x, 1);
	add(1, x, x);
}
void del(int x) {
	x = a[x];
	tmp -= query(0, x - 1) * x - query(1, x - 1);
	tmp -= (query(1, N - 1) - query(1, x)) - (query(0, N - 1) - query(0, x)) * x;
	add(0, x, -1);
	add(1, x, -x);
}
void solve() {
	int n, m;
	cin >> n >> m;
	int dk = sqrt(n);
	for (int i = 1;i <= n;i++) {
		id[i] = (i - 1) / dk + 1;
		cin >> a[i];
	}
	for (int i = 1;i <= m;i++) {
		int l, r;
		cin >> l >> r;
		q[i] = { l,r,i };
	}
	sort(q + 1, q + 1 + m, [&](Q a, Q b) {
		if (id[a.l] == id[b.l])return a.r < b.r;
		return id[a.l] < id[b.l];
		});
	int l = 1, r = 0;
	for (int i = 1;i <= m;i++) {
		while (l > q[i].l) add(--l);
		while (r < q[i].r) add(++r);
		while (l < q[i].l) del(l++);
		while (r > q[i].r) del(r--);
		res[q[i].k] = tmp;
	}
	for (int i = 1;i <= m;i++) cout << res[i] * 2 << endl;

}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
	int _ = 1;
	// cin >> _ ;
	while (_--)
		solve();
	return 0;
}