代码应该挺好看懂，TLE on #17

#include<bits/stdc++.h>
using namespace std;

#define LL long long
const int N = 5e5 + 5;
int n, m, a[N], b[N], len, L[N], R[N];
int nxt[N], lst[N], d[N], l, r, st;
LL res, ans[N];
struct ask{int l, r, id;} q[N];
struct GoBack{int x, lst, nxt;} gb[N];

inline int read() { int x = 0, w = 0; char ch = 0; while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();} while (isdigit(ch)) {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();} return w ? -x : x; }
inline void write(LL x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline bool cmp(ask A, ask B) {return b[A.l] == b[B.l] ? (A.r > B.r) : b[A.l] < b[B.l];}
inline int dis(int x, int y) {if(!x || !y || x == n + 1 || y == n + 1) return 0; return abs(d[x] - d[y]);}
inline void Back(bool flag){
	int a = gb[st].lst, b = gb[st].x, c = gb[st].nxt; --st;
	if(flag) res = res - dis(a, c) + dis(a, b) + dis(b, c);
	lst[b] = a, nxt[b] = c, nxt[a] = b, lst[c] = b;
}
inline void del(int p){
	res = res - dis(lst[p], p) - dis(nxt[p], p) + dis(lst[p], nxt[p]);
	nxt[lst[p]] = nxt[p], lst[nxt[p]] = lst[p];
}
signed main(){
	n = read(), m = read(), len = ceil(n / sqrt(m));
	for(int i = 1; i <= n; ++i){
		a[i] = read(), d[a[i]] = i;
		R[b[i] = (i + len - 1) / len] = i;
		L[b[i]] = !L[b[i]] ? i : L[b[i]]; 
	}
	for(int i = 1; i <= m; ++i) q[i].l = read(), q[i].r = read(), q[i].id = i;
	
	sort(q + 1, q + 1 + m, cmp);
	l = 1, r = n, nxt[0] = 1, lst[n + 1] = n;
	for(int i = 1; i <= n; ++i) lst[i] = i - 1, nxt[i] = i + 1, res += (i > 1) * abs(d[i] - d[i - 1]);
	
	for(int i = 1; i <= m; ++i){
		if(b[q[i].l] != b[q[i - 1].l]){
			while(st) Back(1), ++r;
			while(l < L[b[q[i].l]]) del(a[l++]);
		}
		while(r > q[i].r) gb[++st] = {a[r], lst[a[r]], nxt[a[r]]}, del(a[r--]);
		LL _res = res;
		for(int j = l; j < q[i].l; ++j) gb[++st] = {a[j], lst[a[j]], nxt[a[j]]}, del(a[j]);
		ans[q[i].id] = res, res = _res;
		for(int j = l; j < q[i].l; ++j) Back(0);
	}
	for(int i = 1; i <= m; ++i) write(ans[i]), putchar('\n');
	return 0;
}