#include <bits/stdc++.h>
#define ll long long
#define T 0
using namespace std;
const int mx=5e5+5;
int n,m,col,a[mx],bel[mx],rnk[mx];
ll ans[mx],all,ANS[2];

struct query{
	int l,r,id;
	inline bool operator < (const query &x)const{
		return bel[l]!=bel[x.l]?bel[l]<bel[x.l]:r>x.r;
	}
}q[mx];
struct node{
	int val,id;
	inline bool operator < (const node &x)const{
		return x.val<val;
	}
}b[mx];
struct list{
	int l,r;
}link[mx],orig[mx],last[mx];
inline void del(int i,int id){
	if(T)printf("        del(%d)\n",i);
	if(link[i].l)ANS[id]+=abs(link[i].l-i);
	if(link[i].r)ANS[id]+=abs(link[i].r-i);
	if(link[i].l && link[i].r)ANS[id]-=abs(link[i].l-link[i].r);
	if(link[i].l)link[link[i].l].r=link[i].r;
	if(link[i].r)link[link[i].r].l=link[i].l;
}
inline void add(int i,int j){
	link[i].r=j;link[j].l=i;
	all+=abs(i-j);
}
inline int read(){
	int x=0;char ch=getchar();
	while(ch<48||ch>57)ch=getchar();
	while(48<=ch && ch<=57)x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10|48);
}
inline void init(){
	n=read();m=read();
	col=sqrt(n);for(int i=1;i<=n;++i)bel[i]=(i-1)/col+1;
	for(int i=1;i<=n;++i)b[i].val=a[i]=read(),b[i].id=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);sort(b+1,b+1+n);//O(mlogm+nlogn)
	for(int i=1;i<=n;++i)rnk[b[i].val]=b[i].id;
	for(int i=2;i<=n;++i)add(rnk[i-1],rnk[i]);//O(n)
	if(T){
		printf("  rnk:");for(int i=1;i<=n;++i)printf("%d ",rnk[i]);printf("\n\n");
		printf("  all=%lld\n",all);
	}
}
#define start(x) (x-1)*col+1
#define end(x) x*col
inline void solve(){
	for(int i=1,l=0,r=0,now=0;i<=m;++i){
		int ql=q[i].l,qr=q[i].r,id=q[i].id;
		if(bel[ql]>now){//get to a new column
			if(now){
				memcpy(link,last,sizeof link);//back to last links
				l=start(now);ANS[0]=0;
				while(l<start(bel[ql]))del(l++,0);
				all-=ANS[0];//delete old column
			}
			memcpy(last,link,sizeof link);//save original links
			now=bel[ql];//update column
			r=n;ANS[1]=0;//r.reset
		}//sumO=O(sqrt(n)^2)=O(n)
		l=start(now);ANS[0]=0;//l reset
		
		if(T){
			printf("    id=%d,ql=%d,qr=%d,l=%d,r=%d,all=%lld\n",id,ql,qr,l,r,all);
		}
		
		while(r>qr)del(a[a[r--]],1);//r's contribute continues; sumO=O(nsqrt(n))
		memcpy(orig,link,sizeof link);
		while(l<ql)del(a[a[l++]],0);//l only have a try;sumO=O(msqrt(n))
		memcpy(link,orig,sizeof orig);
		
		if(T){
			printf("      ans0=%lld,ans1=%lld\n",ANS[0],ANS[1]);
		}
		
		ans[id]=all-ANS[0]-ANS[1];//ans=all-deleted
	}//sumO=(n+m)sqrt(n)+(n+m)*memcpy
}


int main()
{
	//freopen("P5906_4.in","r",stdin);freopen("test.in","w",stdout);
	init();
	solve();
	for(int i=1;i<=m;++i)write(ans[i]),puts("");
	return 0;
}

rt

回滚莫队90%数据TLE，delete操作也是O(1)的，是否是memcpy函数效率影响？如果要替换掉memcpy应该怎么存之前的链表？

或者哪位大佬能告诉我哪里有这题的大样例吗qwq